【经典】Noip动态规划

一、线性动态规划

最长严格上升子序列

#include<iostream>

#include<cstdio>

using namespace std;

int n,ans;

int a[],dp[];

int main()

{

    scanf("%d",&n);

    for(int i=;i<=n;i++)

    scanf("%d",&a[i]);

    for(int i=;i<=n;i++)

    {

        for(int j=;j<i;j++)

        {

            if(a[j]<a[i])

            dp[i]=max(dp[i],dp[j]+);

            ans=max(ans,dp[i]);

        }

    }

    printf("%d\n",ans+);

    return ;

}

最长严格上升子序列

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn=0x3f3f3f3f;

int n,a[],dp[];

int main()

{

    scanf("%d",&n);

    for(int i=;i<=n;i++)

    scanf("%d",&a[i]);

    memset(dp,0x3f,sizeof(dp));

    for(int i=;i<=n;i++)

    {

        int p=upper_bound(dp+,dp+n+,a[i])-dp;

        if(a[i]!=dp[p-])//严格上升序列

        dp[p]=a[i];

    }

    for(int i=;i<=n+;i++)

    {

        if(dp[i]==maxn)

        {

            printf("%d\n",i-);

            return ;

        }

    }

    return ;

}

nlogn

变形：打鼹鼠

#include<iostream>

#include<cstdlib>

#include<cstdio>

using namespace std;

int maxt,n,m,ans,x[],y[],t[],f[];

int main()

{

    int i,j;

    scanf("%d%d",&n,&m);

    for (i=;i<=m;++i)

        scanf("%d%d%d",&t[i],&x[i],&y[i]);

    for (i=;i<=m;++i)

    {

        f[i]=;//f表示到第i只鼹鼠出现时最多可以打到多少只

        for (j=i-;j>=;--j)

            if (t[i]-t[j]>=abs(x[i]-x[j])+abs(y[i]-y[j]))

            //如果时间足够，能从j点移动到当前点

                f[i]=max(f[i],f[j]+);

        ans=max(ans,f[i]);

    }

    printf("%d",ans);

}

Luogu打鼹鼠

二、背包

1)01背包

每个物品只有一个且只有选与不选两种可能

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int f[],w[],v[];

int n,m,t;

int main()

{

    scanf("%d",&t);

    while(t--)

    {

        memset(f,,sizeof(f));

        scanf("%d%d",&n,&m);

        for(int i=;i<=n;i++)

        scanf("%d",&v[i]);

        for(int i=;i<=n;i++)

        scanf("%d",&w[i]);

        for(int i=;i<=n;i++)

        for(int j=m;j>=w[i];j--)

        f[j]=max(f[j],f[j-w[i]]+v[i]);

        printf("%d\n",f[m]);

    }

    return ;

}

01背包

2)完全背包

每件物品数量无限

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int w1,w2,wi,t,k,f[],v[],w[];

int main()

{

    scanf("%d",&t);

    while(t--)

    {

        memset(f,0x3f,sizeof(f));

        f[]=; //**

        scanf("%d%d",&w1,&w2);

        wi=w2-w1;

        scanf("%d",&k);

        for(int i=;i<=k;i++)

        scanf("%d%d",&v[i],&w[i]);

        for(int i=;i<=k;i++)

        for(int j=w[i];j<=wi;j++)

        f[j]=min(f[j],f[j-w[i]]+v[i]);

        if(f[wi]==0x3f3f3f3f)

        printf("This is impossible.\n");

        else

        printf("The minimum amount of money in the piggy-bank is %d.\n",f[wi]);

    }

    return ;

}

完全背包

3)多重背包

每个物品数量一定

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int t,mon,k,w[],pri[],f[],cnt[];

int main()

{

    scanf("%d",&t);

    while(t--)

    {

        memset(f,,sizeof(f));

        scanf("%d%d",&mon,&k);

        for(int i=;i<=k;i++)

        scanf("%d%d%d",&pri[i],&w[i],&cnt[i]);

        for(int i=;i<=k;i++)

        {

            for(int j=mon;j>=pri[i];j--)

            {

                for(int h=;h<=cnt[i];h++)

                {

                    if(j-h*pri[i]<)break;

                    f[j]=max(f[j],f[j-h*pri[i]]+h*w[i]);

                }

            }

        }

        printf("%d\n",f[mon]);

    }

    return ;

}

多重背包

4)混合背包

-1为无限个

#include<iostream>

#include<cstdio>

#include<cstdlib>

using namespace std;

int w[],v[],c[],dp[];

int main()

{

    int vv,n;

    scanf("%d%d",&n,&vv);

    for(int i=;i<=n;i++)

    scanf("%d%d%d",&w[i],&v[i],&c[i]);

    for(int i=;i<=n;i++)

    {

        if(c[i]==-)

        {

            for(int j=w[i];j<=vv;j++)

            {

                dp[j]=max(dp[j],dp[j-w[i]]+v[i]);

            }

        }

        else

        {

            int x=c[i];

            for(int j=;j<=x;j<<=)

            {

                for(int k=vv;k>=w[i]*j;k--)

                {

                    dp[k]=max(dp[k],dp[k-w[i]*j]+v[i]*j);

                }

                x-=j;

            }

            if(x!=)

            {

                for(int j=vv;j>=x*w[i];j--)

                {

                    dp[j]=max(dp[j],dp[j-x*w[i]]+v[i]*x);

                }

            }

        }

    }

    printf("%d",dp[vv]);

    return ;

}

混合背包

5)二维费用背包

#include<bits/stdc++.h>

using namespace std;

int f[][];

int main(){

    int n,m,x;

    cin>>n>>m>>x;

    for(int i=;i<=n;i++){

        int a,b,c;

        cin>>a>>b>>c;

        for(int j=m;j>=b;j--)                                     //以下3行是算法的核心

            for(int k=x;k>=c;k--)

                f[j][k]=max(f[j][k],f[j-b][k-c]+a);

    }

    cout<<f[m][x];

    return ;

}

二维费用

6)有依赖性背包问题

#include<iostream>

#include<cstdio>

using namespace std;

struct e

{

    int v,p,q,w,f[];

}g[];

int n,m,f[];

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=;i<=m;i++)

    {

        scanf("%d%d%d",&g[i].v,&g[i].p,&g[i].q);

        g[i].w=g[i].v*g[i].p;

        if(g[i].q!=)

        g[g[i].q].f[++g[g[i].q].f[]]=i;

    }

    for(int i=;i<=m;i++)

    {

        if(g[i].q==)

        {

            int f1=g[i].f[],f2=g[i].f[];

            for(int j=n;j>=g[i].v;j--)

            {

                if(f1&&j-g[f1].v-g[i].v>=)

                f[j]=max(f[j],f[j-g[i].v-g[f1].v]+g[i].w+g[f1].w);

                if(f2&&j-g[f2].v-g[i].v>=)

                f[j]=max(f[j],f[j-g[i].v-g[f2].v]+g[i].w+g[f2].w);

                if(f1&&f2&&j-g[i].v-g[f1].v-g[f2].v>=)

                f[j]=max(f[j],f[j-g[i].v-g[f1].v-g[f2].v]+g[i].w+g[f1].w+g[f2].w);

                f[j]=max(f[j],f[j-g[i].v]+g[i].w);

            }

        }

    }

    printf("%d\n",f[n]);

    return ;

}

依赖性背包

7)01背包求方案数

#include<iostream>

#include<cstdio>

using namespace std;

int f[],n,m,a[];

int main(){

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;i++)scanf("%d",&a[i]);

    f[]=;

    for(int i=;i<=n;i++)

        for(int j=m;j>=a[i];j--)

            f[j]+=f[j-a[i]];

    printf("%d",f[m]);

}

01背包求方案数

三、区间型dp

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int w[],f[][],sum[];

int n;

int main() {

    scanf("%d",&n);

    for(int i=; i<=n; i++) {

        scanf("%d",&w[i]);

        sum[i]=sum[i-]+w[i];

    }

    for(int i=; i<=n; i++)

        for(int j=i-; j>=; j--) {

            f[j][i]=0x3f3f3f3f;

            for(int k=j; k<i; k++)

                f[j][i]=min(f[j][i],f[j][k]+f[k+][i]+sum[i]-sum[j-]);

        }

    printf("%d\n",f[][n]);

    return ;

}

合并果子

四、概率dp

#include<iostream>

#include<cstdio>

using namespace std;

int n;

double dp[][];

int main(){

    scanf("%d",&n);n/=;

    for(int i=;i<=n;i++)dp[i][]=dp[][i]=1.0;

    for(int i=;i<=n;i++)

     for(int j=;j<=n;j++)

      dp[i][j]=(dp[i-][j]+dp[i][j-])/2.0;

    printf("%.4lf\n",dp[n][n]);

    return ;

}

搞笑世界杯

五、多维dp

#include<iostream>

#include<cstdio>

using namespace std;

int n,m,x,maxx,s[],qp[],f[][][][];

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;i++)

    scanf("%d",&qp[i]);

    for(int i=;i<=m;i++)

    {

        scanf("%d",&x);

        if(x==)s[]++;

        if(x==)s[]++;

        if(x==)s[]++;

        if(x==)s[]++;

    }

    f[][][][]=qp[];

    f[][][][]=qp[];

    f[][][][]=qp[];

    f[][][][]=qp[];

    f[][][][]=qp[];

    for(int i=;i<=s[];i++)

    for(int j=;j<=s[];j++)

    for(int l=;l<=s[];l++)

    for(int k=;k<=s[];k++)

    {

        maxx=;

        if(i)maxx=max(maxx,f[i-][j][l][k]);

        if(j)maxx=max(maxx,f[i][j-][l][k]);

        if(l)maxx=max(maxx,f[i][j][l-][k]);

        if(k)maxx=max(maxx,f[i][j][l][k-]);

        f[i][j][l][k]=maxx+qp[i+j*+l*+k*+];

     }

     printf("%d\n",f[s[]][s[]][s[]][s[]]);

    return ;

}

乌龟棋

整理的不全，noip不会考很难的吧。【逃

巴特西

【经典】Noip动态规划

最新文章

热门文章