动态规划 is beginning。。。。。。。。。

感觉动态规划非常模糊，怎么办呢？？？

狂刷题吧！！

！！

！

！！！

！

！！！

！！

！

。！！

。。！。！

PKU PPt

动规解题的一般思路

1. 将原问题分解为子问题

把原问题分解为若干个子问题，子问题和原问题形式同样或类似。仅仅只是规模变小了。

子问题都解决，原问题即解
决(数字三角形例）。
子问题的解一旦求出就会被保存，所以每一个子问题仅仅需求解一次。

2. 确定状态

在用动态规划解题时，我们往往将和子问题相关的各个变量的一组取值，称之为一个“状态”。

一个“状态”相应于一个或多个子问题，所谓某个“状态”下的“值”，就是这个“状态”所相应的子问题的解。

全部“状态”的集合。构成问题的“状态空间”。

“状态空间”的大小，与用动态规划解决这个问题的时间复杂度直接相关。

在数字三角形的样例里，一共同拥有N×(N+1)/2个数字。所以这个问题的状态空间里一共就有N×(N+1)/2个状态。

整个问题的时间复杂度是状态数目乘以计算每一个状态所需时间。
在数字三角形里每一个“状态”仅仅须要经过一次。且在每一个状态上作计算所花的时间都是和N无关的常数。
用动态规划解题，常常碰到的情况是，K个整型变量能构成一个状态（如数字三角形中的行号和列号这两个变量
构成“状态”）。

假设这K个整型变量的取值范围各自是N1, N2, ……Nk，那么。我们就能够用一个K维的数组array[N1] [N2]……[Nk]

来存储各个状态的“值”。

这个“值”未必就是一个整数或浮点数，可能是须要一个结构才干表示的。那么array就能够是一个结构数组。

一个“状态”下的“值”一般会是一个或多个子问题的解。

3. 确定一些初始状态（边界状态）的值

以“数字三角形”为例。初始状态就是底边数字，值就是底边数字值。

4. 确定状态转移方程

定义出什么是“状态”，以及在该 “状态”下的“值”后，就要找出不同的状态之间怎样迁移――即怎样从一个或多个“值”

已知的“状态”，求出还有一个“状态”的“值”(“人人为我”递推型)。

状态的迁移能够用递推公式表示，此递推公式也可被称作“状态转移方程”。

数字三角形的状态转移方程:

能用动规解决的问题的特点

1) 问题具有最优子结构性质。

假设问题的最优解所包括的子问题的解也是最优的。我们就称该问题具有最优子结
构性质。

2) 无后效性。

当前的若干个状态值一旦确定。则此后过程的演变就仅仅和这若干个状态的值有关，和之前是採取哪
种手段或经过哪条路径演变到当前的这若干个状态，没有关系。

1、POJ 2479 Maximum sum

首刷水题！

！

！！

双向统计最大和。

AC代码例如以下：

#include<iostream>
#include<cstring>
#include<cstdio>
#define inf -1000000000
using namespace std;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        int i;
        scanf("%d",&n);
        int a[50005],dp[50005];
        memset(dp,0,sizeof dp);
        for(i=1;i<=n;i++)
            scanf("%d",&a[i]);
        int sum=0;
        int maxx=inf;//须要取到负最小
        for(i=1;i<n;i++)
        {
            sum+=a[i];
            if(sum>maxx)
                maxx=sum;
            dp[i]=maxx;
            if(sum<0)
                sum=0;
        }
        int ans=inf;maxx=inf;sum=0;
        for(i=n;i>1;i--)
        {
            sum+=a[i];
            if(sum>maxx)
                maxx=sum;
            ans=max(ans,maxx+dp[i-1]);
            if(sum<0)
                sum=0;
        }
        cout<<ans<<endl;
    }
    return 0;
}

2、HDU 2059 龟兔赛跑

#include<iostream>
using namespace std;
#define M 10005
#define MAX 0xfffff;

double min(double a,double b)
{
    return a<b?
a:b;
}

int main()
{
    double l,L;
    int n,c;
    double t,t1,t2,ti;
    double vr,v1,v2;
    double p[M],dp[M];
    int i,j;
    while(cin>>l)
    {
        cin>>n>>c>>t>>vr>>v1>>v2;
        for(i=1,p[0]=0,p[n+1]=l;i<=n;i++)
            cin>>p[i];
        dp[0]=0;
        t1=l/vr;t2=c/v1;
        for(i=1;i<=n+1;i++)
        {
            dp[i]=MAX;
            for(j=0;j<i;j++)
            {
                L=p[i]-p[j];
                if(L>c)
                    ti=t2+(L-c)/v2;
                else
                    ti=L/v1;
                if(j)
                    ti+=t;
                dp[i]=min(dp[i],dp[j]+ti);
            }
        }
        if(dp[n+1]>t1)
            cout<<"Good job,rabbit!"<<endl;
        else
            cout<<"What a pity rabbit!"<<endl;

    }
    return 0;
}

3、POJ 1458 Common Subsequence

区间动规，最长公共子序列

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;

int dp[1005][1005];

int main()
{
    int i,j;
    int la,lb;
    char a[1005],b[1005];
    while (~scanf("%s%s",a,b))
    {
        la=strlen(a);
        lb=strlen(b);
        memset(dp,0,sizeof dp);
        for(i=1;i<=la;i++)
        for(j=1;j<=lb;j++)
        {
            if(a[i-1]==b[j-1])
            {
                dp[i][j]=dp[i-1][j-1]+1;
            }
            else {
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
        }

        cout<<dp[la][lb]<<endl;
    }
    return 0;
}

4、POJ 3624 Charm Bracelet

背包水题。！

<pre name="code" class="cpp">#include<iostream>
#include<cstring>
#include<cstdio>
#define ll long long
using namespace std;

int main()
{
    int i,j;
    int n,m;
    int a[5000],b[5000];
    int dp[20000];
    while(~scanf("%d%d",&n,&m))
    {
        for(i=1;i<=n;i++)
        scanf("%d%d",&a[i],&b[i]);
        memset(dp,0,sizeof dp);
        for(i=1;i<=n;i++)
            for(j=m;j>=a[i];j--)
            dp[j]=max(dp[j],dp[j-a[i]]+b[i]);
        cout<<dp[m]<<endl;
    }

    return 0;
}

5、POJ 2486 Apple Tree

经典树形dp！

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;


int n,k;
int ap[205],cont[205];
int trees[205][205];
int dp[2][205][205];
int vis[205];

void dp_trees(int a)
{
    int i,j,l;
    int b;
    for(i=0;i<=k;i++)
        dp[0][a][i]=dp[1][a][i]=ap[a];
    vis[a]=1;
    for(i=1;i<=cont[a];i++)
    {
        b=trees[a][i];
        if(!vis[b])
        {
            dp_trees(b);
            for(j=k;j>=0;j--)
                for(l=0;l<=j;l++)
            {
                dp[0][a][j+2]=max(dp[0][a][j+2],dp[0][b][l]+dp[0][a][j-l]);
                dp[1][a][j+2]=max(dp[1][a][j+2],dp[0][b][l]+dp[1][a][j-l]);
                dp[1][a][j+1]=max(dp[1][a][j+1],dp[1][b][l]+dp[0][a][j-l]);
            }
        }
    }
}


int main()
{
    int i,j;
    int a,b;
    while(cin>>n>>k)
    {
        memset(ap,0,sizeof ap);
        memset(cont,0,sizeof cont);
        memset(trees,0,sizeof trees);
        memset(vis,0,sizeof vis);
        for(i=1;i<=n;i++)
            cin>>ap[i];
        for(i=1;i<n;i++)
        {
            cin>>a>>b;
            trees[a][++cont[a]]=b;
            trees[b][++cont[b]]=a;
        }
        memset(dp,0,sizeof dp);
        dp_trees(1);
        cout<<dp[1][1][k]<<endl;
    }
    return 0;
}

6、POJ 2533 Longest Ordered Subsequence

最长递增子序列。O(n*n)算法。。

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;


int main()
{
    int i,j;
    int t;
    int n;
    int dp[40005];
    int a[40005];
    while(cin>>n)
    {
        for(i=1;i<=n;i++)
            {
                cin>>a[i];
                dp[i]=1;
            }
        for(i=2;i<=n;i++)
        {
            for(j=i-1;j>=1;j--)
            {
                if(a[i]>a[j])
                    dp[i]=max(dp[i],dp[j]+1);
            }
        }
        int maxx=0;
        for(i=1;i<=n;i++)
            if(dp[i]>maxx)
                maxx=dp[i];
        cout<<maxx<<endl;
    }
    return 0;
}

7、POJ 1631 Bridging signals

最长递增子序列！

O(nlogn)算法！。

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

int dp[40005];
int a[40005];

int dich(int l,int r,int i)
{
    int mid;
    while(r>l)
    {
        mid = (l+r)/2;
        if(a[i]<=dp[mid]) r=mid;
        else l=mid+1;
    }
    return l;
}

int main()
{
    int i,j;
    int t;
    int n;
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(i=1;i<=n;i++)
            {
                cin>>a[i];
            }
            dp[1]=a[1];
            int top=1;
        for(i=2;i<=n;i++)
        {
            if(a[i]>dp[top])
            {
                dp[++top]=a[i];
            }
            else
            {
                int ans=dich(1,top,i);
                dp[ans]=a[i];
            }
        }
        cout<<top<<endl;
    }
    return 0;
}

8、POJ 1836 Alignment

双向找最长递增子序列就可以！

！

。

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int main()
{
    int n;
    int i,j;
    double a[1005];
    int l[1005],r[1005];
    while(cin>>n)
    {
        for(i=1;i<=n;i++)
            cin>>a[i];
        memset(l,0,sizeof l);
        memset(r,0,sizeof r);
        for(i=1;i<=n;i++)
        {
            l[i]=1;
            r[i]=1;
        }
        for(i=2;i<=n;i++)
        {
            for(j=i-1;j>=1;j--)
            {
                if(a[j]<a[i])
                    l[i]=max(l[i],l[j]+1);
            }
        }
        for(i=1;i<=n;i++)
            if(l[i]<l[i-1])
            l[i]=l[i-1];
        for(i=n-1;i>=1;i--)
        {
            for(j=i+1;j<=n;j++)
                if(a[j]<a[i])
                r[i]=max(r[i],r[j]+1);
        }
        for(i=n;i>=1;i--)
            if(r[i]<r[i+1])
            r[i]=r[i+1];
        int ans=0;
        for(i=0;i<=n+1;i++)
            ans=max(ans,l[i]+r[i+1]);

        cout<<n-ans<<endl;
    }
    return 0;
}

9、POJ 1080 Human Gene Functions

#include<iostream>
#include<cstring>
using namespace std;

int map[10][10]={{0,-3,-4,-2,-1},
                 {-3,5,-1,-2,-1},
                 {-4,-1,5,-3,-2},
                 {-2,-2,-3,5,-2},
                 {-1,-1,-2,-2,5}};
int main()
{
    int t;
    cin>>t;
    while (t--)
    {
        int i,j;
        char a[105],b[105];
        int aa[105],bb[105];
        int la,lb;
        cin>>la>>a>>lb>>b;
        for(i=0;i<la;i++)
        {
            if(a[i]=='A')
            aa[i]=1;
            if(a[i]=='C')
            aa[i]=2;
            if(a[i]=='G')
            aa[i]=3;
            if(a[i]=='T')
            aa[i]=4;
        }
        for(i=0;i<lb;i++)
        {
            if(b[i]=='A')
            bb[i]=1;
            if(b[i]=='C')
            bb[i]=2;
            if(b[i]=='G')
            bb[i]=3;
            if(b[i]=='T')
            bb[i]=4;
        }
        int dp[105][105];
        memset(dp,0,sizeof dp);
        for(i=1;i<=la;i++)
            dp[i][0]=dp[i-1][0]+map[aa[i-1]][0];
        for(i=1;i<=lb;i++)
            dp[0][i]=dp[0][i-1]+map[0][bb[i-1]];
        for(i=1;i<=la;i++)
        {
            for(j=1;j<=lb;j++)
            {
                dp[i][j]=max(dp[i-1][j]+map[aa[i-1]][0],dp[i][j-1]+map[0][bb[j-1]]);
                dp[i][j]=max(dp[i][j],dp[i-1][j-1]+map[aa[i-1]][bb[j-1]]);
            }
        }
        cout<<dp[la][lb]<<endl;
    }
    return 0;
}

10、HDU 1024 Max Sum Plus Plus

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define inf -1000000000
using namespace std;

int dp[1000005],pr[1000005];
int a[1000005];

int main ()
{
    int n,m;
    int i,j;
    int maxx;
    while(~scanf("%d%d",&m,&n))
    {
        for(i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
        memset(dp,0,sizeof dp );
        memset(pr,0,sizeof pr);
        for(i=1;i<=m;i++)
        {
            maxx=inf;
            for(j=i;j<=n;j++)
            {
                dp[j]=max(dp[j-1]+a[j],pr[j-1]+a[j]);
                pr[j-1]=maxx;
                maxx=max(maxx,dp[j]);
            }
        }
        printf("%d
",maxx);
    }
    return 0;
}

11、HDU 1231 最大连续子序列

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#define inf -1000000000
using namespace std;
int main()
{
    int n;
    int i,j;
    int a[10005];
    while(~scanf("%d",&n)&&n)
    {
        for(i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
        int l,r,bj=1;
        l=1;r=1;bj=1;
        int sum=0;
        int maxx=inf;
        int cont=0;
        for(i=1;i<=n;i++)
        {
            sum+=a[i];

            if(sum>maxx)
            {
                maxx=sum;
                l=bj;
                r=i;
            }
            if(sum<0)
            {
                cont++;
                sum=0;
                bj=i+1;
            }
        }
        if(sum>maxx)
            {
                maxx=sum;
                l=bj;
                r=i;
            }
        if(cont==n)
            printf("0 %d %d
",a[1],a[n]);
        else
        printf("%d %d %d
",maxx,a[l],a[r]);

    }
    return 0;
}

12、HDU 1503 Advanced Fruits

最长公共序列的路径记忆！！！

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;


char a[105],b[105];
int bj[105][105];
int dp[105][105];

void pri(int l,int r)
{
    if(l==0&&r==0) return ;
    if(bj[l][r]==1) {pri(l,r-1);cout<<b[r];}
    else if(bj[l][r]==3) {pri(l-1,r);cout<<a[l];}
    else {pri(l-1,r-1);cout<<a[l];}
}

int main()
{
    int i,j;
    while(~scanf("%s%s",a+1,b+1))
    {
        int la=strlen(a+1);
        int lb=strlen(b+1);
        memset(dp,0,sizeof dp);
        memset(bj,0,sizeof bj);
        for(i=0;i<=la;i++)
            bj[i][0]=3;
        for(i=0;i<=lb;i++)
            bj[0][i]=1;
        for(i=1;i<=la;i++)
        {
            for(j=1;j<=lb;j++)
            {

                if(a[i]==b[j])
                   {
                       dp[i][j]=dp[i-1][j-1]+1;
                       bj[i][j]=2;
                   }
                else
                {
                    if(dp[i][j-1]>dp[i-1][j])
                    {
                        dp[i][j]=dp[i][j-1];
                        bj[i][j]=1;
                    }
                    else {
                        dp[i][j]=dp[i-1][j];
                        bj[i][j]=3;
                    }
                }
            }
        }
        pri(la,lb);
        cout<<endl;

    }
    return 0;
}

13、HDU 1058 Humble Numbers

数位水题！

！。

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define inf 2000000000
#define mod 1000000007
using namespace std;

int main()
{
    int a,b,c,d;
    int n,i;
    int s[10005];
    a=b=c=d=1;
    s[1]=1;
    for(i=2;i<=5842;i++)
        {
            s[i]=min(s[a]*2,min(s[b]*3,min(s[c]*5,s[d]*7)));
            if(s[i]==s[a]*2)
                a++;
            if(s[i]==s[b]*3)
                b++;
            if(s[i]==s[c]*5)
                c++;
            if(s[i]==s[d]*7)
                d++;
        }
    while(~scanf("%d",&n)&&n)
    {
        if(n%10==1&&n%100!=11)
            printf("The %dst humble number is %d.
",n,s[n]);
        else if(n%10==2&&n%100!=12)
            printf("The %dnd humble number is %d.
",n,s[n]);
        else if(n%10==3&&n%100!=13)
            printf("The %drd humble number is %d.
",n,s[n]);
        else
        printf("The %dth humble number is %d.
",n,s[n]);
    }
    return 0;
}

14、HDU 3466 Proud Merchants

背包好题！

。！

！！值得一做！！！！

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define M 10010
using namespace std;

struct H
{
    int p,q,v;
}a[505];

bool cmp(H a,H b)
{
    return a.q-a.p<b.q-b.p;
}

int dp[5005];

int main()
{
    int i,j;
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
        memset(dp,0,sizeof dp);
        for(i=0;i<n;i++)
            scanf("%d%d%d",&a[i].p,&a[i].q,&a[i].v);
        sort(a,a+n,cmp);
        for(i=0;i<n;i++)
            for(j=m;j>=a[i].p&&j>=a[i].q;j--)
            dp[j]=max(dp[j],dp[j-a[i].p]+a[i].v);
        printf("%d
",dp[m]);
    }
    return 0;
}

14、HDU 3555 Bomb

数位基础训练開始。！

！！！

！！

！

我待水似流年，流年带我似水

15、HDU 2086 不要62

我待水似流年，流年待我似水

16、ACdream 1064 完美数

到这我都用了经典dp和记忆化搜索做，后面的记忆化搜索好理解一些

我待水似流年，流年待我似水

17、HDU 3652 B-number