2019-07-29 20:58 已编辑 C++

关注

HPU Summer Day 13

今天讲了一点关于DP的知识和几道例题，据说这样就算是入门了。今天的题怎么说呢？亏是之前做过，要是之前没做过，还真不知道该怎么写。dp就是玄学？
今天的题很多都是需要灵光一现（或者百度解题的。具体的我也说不清，自己体会吧。（怎么能告诉你是因为我不会呢？

The King’s Ups and Downs

Description:
The king has guards of all different heights. Rather than line them up in increasing or decreasing height order, he wants to line them up so each guard is either shorter than the guards next to him or taller than the guards next to him (so the heights go up and down along the line). For example, seven guards of heights 160, 162, 164, 166, 168, 170 and 172 cm. could be arranged as:

or perhaps:

The king wants to know how many guards he needs so he can have a different up and down order at each changing of the guard for rest of his reign. To be able to do this, he needs to know for a given number of guards, n, how many different up and down orders there are:

For example, if there are four guards: 1, 2, 3,4 can be arrange as:

1324, 2143, 3142, 2314, 3412, 4231, 4132, 2413, 3241, 1423

For this problem, you will write a program that takes as input a positive integer n, the number of guards and returns the number of up and down orders for n guards of differing heights.

Input

The first line of input contains a single integer P, (1 <= P <= 1000), which is the number of data sets that follow. Each data set consists of single line of input containing two integers. The first integer, D is the data set number. The second integer, n (1 <= n <= 20), is the number of guards of differing heights.

Output

For each data set there is one line of output. It contains the data set number (D) followed by a single space, followed by the number of up and down orders for the n guards.

Sample Input

4
1 1
2 3
3 4
4 20

Sample Output

1 1
2 4
3 10
4 740742376475050

Problem solving:
这道题我是真的懵逼了。。。
看这个大佬的解释吧:niuox
题意是求1-n 的全排列中有多少呈现高低高低高低或者地高低高形式排列的个数。

这种排列叫做：alternating permutations 或者 Extremal Permutations 。

可以用DP做。

dp(n,k)表示：长度为n，最后一个数为k，最后两个数是递增的排列的个数;

dp2(n,k)表示：长度为n,最后一个数为k,最后两个数是递减的排列的个数;

那么：

dp(n,k) = dp2(n,n+1-k) ;

很好理解吧，比如说132(低高低)等价于312(高低高)，相对的位置加起来等于4.

那么我们针对dp[n][k]的最后一位进行如下考虑：

最后一位是k，因为dp[n][k]最后两个数字是递增的，所以第n-1位的最大值是k-1。那么我们很容易推导出DP方程：

又

所以：dp(n,k) = dp(n-1,n+1-k) + dp(n,k-1)；
Code:

#include<bits/stdc++.h>
using namespace std;
const int maxn=25;
typedef long long ll;
ll dp[maxn][maxn],ans[maxn];
void init()
{
    dp[1][1]=1;ans[1]=1;
    for(int i=2;i<=20;i++)
    {
        for(int k=2;k<=i;k++)
        {
            dp[i][k]=dp[i-1][i+1-k]+dp[i][k-1];
            ans[i]+=dp[i][k];
        }
        ans[i]*=2;
    }
}
int main()
{
    init();
    int p,m,n;
    cin>>p;
    while(p--)
    {
        cin>>m>>n;
        cout<<m<<" "<<ans[n]<<endl;
    }
}

数塔

Description:
在讲述DP算法的时候，一个经典的例子就是数塔问题，它是这样描述的：

有如下所示的数塔，要求从顶层走到底层，若每一步只能走到相邻的结点，则经过的结点的数字之和最大是多少？

已经告诉你了，这是个DP的题目，你能AC吗?

Input

输入数据首先包括一个整数C,表示测试实例的个数，每个测试实例的第一行是一个整数N(1 <= N <= 100)，表示数塔的高度，接下来用N行数字表示数塔，其中第i行有个i个整数，且所有的整数均在区间[0,99]内。

Output

对于每个测试实例，输出可能得到的最大和，每个实例的输出占一行。

Sample Input

1
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

Sample Output

30

Problem solving:
挺简单的一道经典的dp的题。这道题我们可以倒着推，状态转移方程就是
a[i][j]=max(a[i+1][j],a[i+1][j+1])+a[i][j]
按照这个处理完之后直接输出a[1][1]即可

Code:

#include<bits/stdc++.h>
using namespace std;
const int maxn = 105;
int c,n,a[maxn][maxn],ans[maxn][maxn];
int main()
{
    cin>>c;
    while(c--)
    {
        memset(ans,0,sizeof(ans));
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=i;j++)
                cin>>a[i][j];
        }
        for(int i=n-1;i>=1;i--)
        {
            for(int j=1;j<=i;j++)
            {
                a[i][j]=max(a[i+1][j],a[i+1][j+1])+a[i][j];
            }
        }
        cout<<a[1][1]<<endl;
    }
}

母牛的故事

Description:
有一头母牛，它每年年初生一头小母牛。每头小母牛从第四个年头开始，每年年初也生一头小母牛。请编程实现在第n年的时候，共有多少头母牛？
Input

输入数据由多个测试实例组成，每个测试实例占一行，包括一个整数n(0<n<55)，n的含义如题目中描述。
n=0表示输入数据的结束，不做处理。

Output

对于每个测试实例，输出在第n年的时候母牛的数量。
每个输出占一行。

Sample Input

2
4
5
0

Sample Output

2
4
6

Problem solving:
经典题。每头小母牛从第四年开始就可以每年生一头小牛，所以第n年牛的个数即为
a[n]=a[n-1]+a[n-3]
即状态转移方程。a[n-1]代表的是上一年所有的母牛，a[n-3]代表的是上一年所有的母牛能生出来的小牛的个数。

Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ans[60];
int main()
{
    ans[0]=0;ans[1]=1;ans[2]=2;ans[3]=3;ans[4]=4;
    for(int i=5;i<60;i++)
        ans[i]=ans[i-1]+ans[i-3];
    int n;
    while(cin>>n&&n)
    {
        cout<<ans[n]<<endl;
    }
}

一只小蜜蜂...

Description:
有一只经过训练的蜜蜂只能爬向右侧相邻的蜂房，不能反向爬行。请编程计算蜜蜂从蜂房a爬到蜂房b的可能路线数。
其中，蜂房的结构如下所示。

Input

输入数据的第一行是一个整数N,表示测试实例的个数，然后是N 行数据，每行包含两个整数a和b(0<a<b<50)。

Output

对于每个测试实例，请输出蜜蜂从蜂房a爬到蜂房b的可能路线数，每个实例的输出占一行。

Sample Input

2
1 2
3 6

Sample Output

1
3

Problem solving:
状态转移方程
ans[i]=ans[i-1]+ans[i-2]

要到达一个蜂房，如果这个蜂房在第一排，只能从它左边的蜂房或者左下方的蜂房过来；如果这个蜂房在第二排，只能从它左边的蜂房或者左上方的蜂房过来。（摘自csdn）

Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ans[55];
int main()
{
    int n,a,b;
    cin>>n;
    ans[1]=1,ans[2]=1,ans[3]=2;
    for(int i=4;i<50;i++)
        ans[i]=ans[i-1]+ans[i-2];
    while(n--)
    {
        cin>>a>>b;
        cout<<ans[b-a+1]<<endl;
    }
}

超级楼梯

Description:
有一楼梯共M级，刚开始时你在第一级，若每次只能跨上一级或二级，要走上第M级，共有多少种走法？
Input

输入数据首先包含一个整数N，表示测试实例的个数，然后是N行数据，每行包含一个整数M（1<=M<=40）,表示楼梯的级数。

Output

对于每个测试实例，请输出不同走法的数量

Sample Input

2
2
3

Sample Output

1
2

Problem solving:
每次能走一级台阶或者两级台阶。所以状态转移方程就是
ans[i]=ans[i-1]+ans[i-2]

Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ans[45];
int main()
{
    ans[1]=0;
    ans[2]=1;
    ans[3]=2;
    for(int i=4;i<=40;i++)
        ans[i]=ans[i-1]+ans[i-2];
    int n,m;
    cin>>n;
    while(n--)
    {
        cin>>m;
        cout<<ans[m]<<endl;
    }
}

Tickets

Description:
现在有n个人要买电影票，如果知道每个人单独买票花费的时间，还有和前一个人一起买花费的时间，问最少花多长时间可以全部买完票。
Input

给出 N(1<=N<=10)，表示有N组样例　　　　给出K (1<=K<=2000)，表示有K个人买票.. 　　　　给出K个数表示这个人单独买票会花的时间..保证每个数 (0s<=Si<=25s) 　　　　给出K-1个数，表示这个人和前面那个人一起买票会花的时间..保证每个数 (0s<=Si<=50s)

Output

对于每一组数据，你需要给出电影院售票结束的时间，售票开始的时间为 08:00:00 am. 时间格式为： HH:MM:SS am|pm. 具体看样例输出

Sample Input

2
2
20 25
40
1
8

Sample Output

08:00:40 am
08:00:08 am
Problem solving:
这道题也是只要找到状态转移方程就行。状态转移方程
ans[i]=min(ans[i-1]+s[i],ans[i-2]+d[i]);
s[i]是一个人单独买票用的时间，d[i]是两个人一起买票用的时间

Code:

#include<bits/stdc++.h>
using namespace std;
const int maxn=2005;
int s[maxn],d[maxn],ans[maxn];
int main()
{
    int n,k;
    cin>>n;
    while(n--)
    {
        cin>>k;
        for(int i=1;i<=k;i++)    cin>>s[i];
        for(int j=2;j<=k;j++)    cin>>d[j];
        ans[1]=s[1];        
        for(int i=2;i<=k;i++)
        {
            ans[i]=min(ans[i-1]+s[i],ans[i-2]+d[i]);
        }
        int time=ans[k];int h,m,s;
        h=time/3600;
        m=time%3600/60;
        s=time%3600%60;
        h+=8;
        if(h<=12)
        printf("%02d:%02d:%02d am\n",h,m,s);
        else
        printf("%02d:%02d:%02d pm\n",h-12,m,s);
    }
}

钱币兑换问题

Description:
在一个国家仅有1分，2分，3分硬币，将钱N兑换成硬币有很多种兑法。请你编程序计算出共有多少种兑法。
Input

每行只有一个正整数N，N小于32768。

Output

对应每个输入，输出兑换方法数。

Sample Input

2934
12553

Sample Output

718831
13137761

Problem solving:
emm，这道题我之前在牛客上面遇见过一道类似的题。只不过那道题里面硬币的个数比这个多。直接套着板子写了、、、

这是个很基础的背包问题，怎么解释交给时间吧，等我理解了就把这个坑填上。

Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=35000;
ll ans[maxn];
ll co[4]={1,2,3};
ll solve(ll x)
{
    ans[0]=1;
    for(int i=0;i<3;i++)
    {
        for(int j=co[i];j<=x;j++)
        {
            ans[j]=(ans[j]+ans[j-co[i]]);
        }
    }
    return ans[x];
}
int main()
{
    ll n;
    while(cin>>n)
    {
        memset(ans,0,sizeof(ans));
        cout<<solve(n)<<endl;
    }
}

Ignatius and the Princess IV

Description:
给你n个数字，请你找出出现至少(n+1)/2次的数字。
输入

本题包含多组数据，请处理到EOF：
每组数据包含两行。
第一行一个数字N(1<=N<=999999) ，保证N为奇数。
第二行为N个用空格隔开的整数。

输出

对于每组数据，输出一行，表示要求找到的那个数

样例输入

5
1 3 2 3 3
11
1 1 1 1 1 5 5 5 5 5 5
7
1 1 1 1 1 1 1

样例输出

3
5
1

Problem solving:
这道题没啥说的，找就完了，可以边输入边查找。
还有很多办法，比如说直接排序。还有dp的方法。

Code:

#include<bits/stdc++.h>
using namespace std;
int n,flag[1000000];
int main()
{
    while(cin>>n)
    {
        int ans,a;
        for(int i=0;i<n;i++)
        {
            cin>>a;
            flag[a]++;
            if(flag[a]>=(n+1)/2)
                ans=a;
        }
        cout<<ans<<endl;
    }
}

最少拦截系统

Description:
某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统.但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能超过前一发的高度.某天,雷达捕捉到敌国的导弹来袭.由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹.
怎么办呢?多搞几套系统呗!你说说倒蛮容易,成本呢?成本是个大问题啊.所以俺就到这里来求救了,请帮助计算一下最少需要多少套拦截系统.
Input

输入若干组数据.每组数据包括:导弹总个数(正整数),导弹依此飞来的高度(雷达给出的高度数据是不大于30000的正整数,用空格分隔)

Output

对应每组数据输出拦截所有导弹最少要配备多少套这种导弹拦截系统.

Sample Input

8 389 207 155 300 299 170 158 65

Sample Output

2

Problem solving:
这个题我一开始就没读懂。。。
以后每一发炮弹都不能超过前一发的高度，所以这个就是求最大上升子序列的长度。
给定排好序的一堆数列中，求其的LIS长度。它的LIS长度就是它非上升子序列的个数。
我比较喜欢用这种nlog(n)的写法

这道题还有一个坑点就是
如果此时一个数大于它前面那个数，那么拦截系统就要加一，但是并不代表前面那个系统就没用了。这样说比较抽象，举个栗子

100 60 80 20 50

我们来看一下，一开始我们选择100，大于60，换成了60，然后我们遇到了80，此时就需要一个新的系统了，然后现在是80，我们接着往下看遇到了20，再换成20，然后遇到了50，现在的50是大于20没错，但是上一个变成60的系统还可以使用，所以答案是2.

也就是因为这个所以不可以直接查找遇见大于前面那个数的情况就加一，这也是这个LIS以及dp的巧妙之处！

Code:

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
const int INF = 0x3f3f3f3f;
int a[maxn],dp[maxn],n;
int main()
{
    int pos;
    while(cin>>pos)
    {
        fill(dp,dp+pos,INF);
        for(int i=0;i<pos;i++)    cin>>a[i];
        for(int i=0;i<pos;i++)
        {
            *lower_bound(dp,dp+pos,a[i])=a[i];
        }
        cout<<lower_bound(dp,dp+pos,INF)-dp<<endl;    
    }
}