动态规划_牛客博客

hdu 1024

题意：给你n个数，要你在这n个数中取m段数（每段无交集），使这m段之和最大。
思路：状态 $dp[i][j]$ 表示取i段以j结尾时能取到的最大和，状态转移方程 $dp[i][j]=max(dp[i-1][k],dp[i][j-1])+a[i]$ ， $dp[i-1][k]$ 表示第j个数单独成一段， $dp[i][j-1]+a[i]$ 表示第j个数不单独成一段。n、m比较大，明显要用滚动数组，就有 $dp[j-1]==dp[i][j-1]$ ，这时我们还要维护（注意一下位置就很好做到）一个一维数组pre[j-1],此时就有 $pre[j-1]==dp[i-1][k]，k<j$ 。
Code：

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define  js  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
int dp[1000005],a[1000005],pre[1000005];
int temp,n,m;
int main() {
    js;
    while(cin>>m>>n) {
        for(int i=1;i<=n;++i) {
            cin>>a[i];
            pre[i]=0;
            dp[i]=0;
        }
        for(int i=1;i<=m;++i) {
            temp=-inf;
            for(int j=i;j<=n;++j) {
                dp[j]=max(dp[j-1],pre[j-1])+a[j];
                pre[j-1]=temp;
                temp=max(temp,dp[j]);
            }
        }
        cout<<temp<<endl;
    }
}

hdu 2018

题意：有一头母牛，它每年年初生一头小母牛。每头小母牛从第四个年头开始，每年年初也生一头小母牛。请编程实现在第n年的时候，共有多少头母牛？
思路：诞生的那一年就算是一年，从第四个年头开始，也就是过了三年就可以生了，默认初始是第一年。然后写出前几项就不难了：
年份： 1 2 3 4 5 6 7
母牛个数: 1 2 3 4 6 9 13
递推式明显就是f[n]=f[n-1]+f[n-3]，这种式子用矩阵快速幂最好。

#include<iostream>
using namespace std;
int a[100];
int main()
{
    int n;
    a[1]=1;
    a[2]=2;
    a[3]=3;
    a[4]=4;
    for(int i = 5; i <= 80; i++)
        a[i] = a[i-1] + a[i-3];
    while(cin >> n && n)
        cout << a[n] << endl;
    return 0;
}

hdu 2050

我们要求的是n条折线分割平面的最大数目。
还是看别人的推导吧 $\Rightarrow$ 传送门
图片说明
Code:

#include<stdio.h>
int main()
{
    __int64 aa[10001]={0,2,7,16};
    int i,n,m;
    scanf("%d",&n);
    while(n--)
    {
        scanf("%d",&m);
        for(i=4;i<=m;i++)
        {
            aa[i]=aa[i-1]+4*i-3;
        }
        printf("%I64d\n",aa[m]);
    }
    return 0;
}

hdu 2182

题意：有一只青蛙，有n个节点，开始时在0节点，有k次往右跳的机会，每次跳的距离是a-b之间。每个节点有一个值，到达那个节点则总值加上那个值。求最大能得到的值。
思路： $dp[i][j]$ 表示第i个节点，第j次跳跃得到的最大值。

$dp[0][0] = a[0]$ 。因为第0个节点不用跳就能得到。
Code：

#include<stdio.h>
#include<string.h>
#define max(a,b)(a)>(b)?(a):(b)
int dp[200][103];
int a[102];
int main() {
    int t,i,j,n,l,r,k,z;
    scanf("%d",&t);
    while(t--) {
        scanf("%d%d%d%d",&n,&l,&r,&k);
        memset(dp,0,sizeof(dp));
        for(i=0;i<n;i++)
        scanf("%d",&a[i]);
        dp[0][0]=a[0];
        int res=0;
        for(i=0;i<=n-l;i++)
        for(j=i+l;j<=i+r;j++)
        for(z=1;z<=k;z++) {
            if(z!=1&&!dp[i][z-1])    break;
                dp[j][z]=max(dp[j][z],dp[i][z-1]+a[j]);
                res=dp[j][z]>res?dp[j][z]:res;
            }
        printf("%d\n",res);
    }
    return 0;
}

hdu 4489

题意：给了你n名不同身高的士兵，求有多少种方法是把他们按波浪状（高低高或低高低）排列。既然是要按波浪状排列，而且士兵的身高有各不相同。
思路：假设n个人身高从1到n升序排列，我们先把题目分解成一个最小子问题，就是第n个人要插在哪里? 他前面有n-1人，那么就有n个孔等着他插，假设他插到了第j个位置,前面有j-1人，后面有n-j人。前面j-1个人的最后两个人肯定是降序的，后面n-j个人的前面两个一定是升序的。n-1个人中选出j个人排在第n个人右边有 $C_{n-1}^{j}$ 中方案，假设 $dp[n][0]$ 表示n个士兵排序最后两个人降序的方案数、 $dp[n][1]$ 表示n个士兵排序前面两个人升序的方案数，由对称性可以知道 $dp[n][0]=dp[n][1]=$ n个人波浪排序的方案总数/2。回到前面，n个人波浪排序的方案总数就是 $\sum_{j=0}^{n-1}{ (dp[j][0]*dp[n-1-j]*C_{n-1}^{j}) }$ 。
Code：

#include<bits/stdc++.h>
#define  js  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define ll long long
using namespace std;
ll c[20][20],dp[21][2];
void init() {
    for(int i=1;i<20;++i) {
        c[i][0]=c[i][i]=1;
        for(int j=1;j<i;++j)
            c[i][j]=c[i-1][j]+c[i-1][j-1];
    }
    dp[0][0]=dp[0][1]=dp[1][0]=dp[1][1]=1;
    for(int i=2;i<=20;++i) {
        ll ans=0;
        for(int k=0;k<i;++k)
            ans+=dp[k][0]*dp[i-1-k][1]*c[i-1][k];
        dp[i][0]=dp[i][1]=ans/2;
    }
}
int t,cnt,n;
int main() {
    js;
    init();
    cin>>t;
    while(t--) {
        cin>>cnt>>n;
        if(n==1)    cout<<cnt<<" 1"<<endl;
        else cout<<cnt<<" "<<(dp[n][0]<<1)<<endl;
    }
}