动态规划 内容总结相关代码

作者： 作者的头像   幼稚园茶茶子 ,  2021-08-20 10:42:12 ,  所有人可见 ,  阅读 329

3


本文是对于分享动态规划 内容总结（已完结）的代码补充。

目录

$1.1$ 背包问题

  • $1.1.1$ $0/1$背包问题

  • $1.1.2$ 完全背包问题

  • $1.1.3$ 多重背包问题

  • $1.1.4$ 多重背包问题的二进制拆分

$1.2$ 区间DP

  • $1.2.1$ 石子合并

  • $1.2.2$ 环形石子合并

$1.4$ 树形DP

  • $1.4.1$ 树的最长距离

  • $1.4.2$ 树形DP与背包问题结合

$1.6$ 单调队列优化DP

  • $1.6.1$ 围栏

  • $1.6.2$ 跳房子

$1.1$ 背包问题

$1.1.1$ $0/1$背包问题

#include<iostream>
#include<cstdio>
using namespace std;
int n,m;
int f[1010]={0};
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        int v,w;
        cin>>v>>w;
        for(int j=m;j>=v;j--)
        f[j]=max(f[j],f[j-v]+w);
    }
    printf("%d\n",f[m]);
    return 0;
}
  • $1.1.2$ 完全背包问题
#include<iostream>
#include<cstdio>
using namespace std;
int n,m,f[1010]={0};
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        int v,w;
        scanf("%d%d",&v,&w);
        for(int j=v;j<=m;j++)
        f[j]=max(f[j],f[j-v]+w);
    }
    printf("%d\n",f[m]);
    return 0;
}
  • $1.1.3$ 多重背包问题
#include<iostream>
#include<cstdio>
using namespace std;
int n,m,v,w,num,f[10000]={0};
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d%d",&v,&w,&num);
        for(int x=1;x<=num;x++)
        for(int y=m;y>=v;y--)
        f[y]=max(f[y],f[y-v]+w);
    }
    cout<<f[m];
    return 0;
}
  • $1.1.4$ 多重背包问题的二进制拆分
#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e5+10;
int n,m,cnt=0;
int v[N],w[N],f[N];

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        for(int j=1;j<=c;j<<=1)
        {
            w[++cnt]=j*a,v[cnt]=j*b;
            c-=j;
        }
        if(c) w[++cnt]=c*a,v[cnt]=c*b;
    }

    for(int i=1;i<=cnt;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 0;
}

$1.2$ 区间DP

  • $1.2.1$ 石子合并
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=310;
int n,f[N][N],s[N];
int main()
{
    memset(f,0x7f,sizeof f);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&s[i]);
        s[i]+=s[i-1];
    }

    for(int i=1;i<=n;i++)
    for(int j=i;j>0;j--)
        f[i][j]=0;
    for(int len=1;len<n;len++)
    {
        for(int l=1;l+len<=n;l++)
        {
            int r=l+len;
            for(int k=1;k<r;k++)
            f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1]);
        }
    }
    printf("%d\n",f[1][n]);
    return 0;
}
  • $1.2.2$ 环形石子合并
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=500;
int n,m,h[N],f[N][N],g[N][N],sum[N];

int main()
{
    scanf("%d",&n);
    memset(f,0x3f,sizeof f);
    memset(g,-0x3f,sizeof g);
    for(int i=1;i<=n;i++) scanf("%d",&h[i]);
    for(int i=1;i<=n;i++) sum[i]=sum[i-1]+h[i];
    for(int i=n+1;i<=n<<1;i++) sum[i]=sum[i-1]+h[i-n];

    for(int len=1;len<=n;len++)
    for(int l=1;l+len-1<=n<<1;l++)
    {
        int r=l+len-1;
        if(l==r) f[l][r]=g[l][r]=0;
        else for(int k=l;k<r;k++)
        {
            f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+sum[r]-sum[l-1]);
            g[l][r]=max(g[l][r],g[l][k]+g[k+1][r]+sum[r]-sum[l-1]);
        }
    }
    int minn=0x3f3f3f3f,maxn=-0x3f3f3f3f;
    for(int i=1;i<=n;i++)
    {
        minn=min(f[i][n+i-1],minn);
        maxn=max(maxn,g[i][n+i-1]);
    }
    printf("%d\n%d\n",minn,maxn);
    return 0;
}

$1.4$ 树形DP

  • $1.4.1$ 树的最长距离
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=2e4+10;
int n,p[N];
int h[N],rh[N],e[N],ne[N],idx=0;
LL w[N],f[N][3];

void add(int a,int b,LL c)
{
    e[++idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx;
}

void dp1(int u,int fa)
{
    f[u][0]=0,f[u][1]=0;
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(j==fa) continue;
        dp1(j,u);
        if(f[u][0]<=f[j][0]+w[i])
        {
            f[u][1]=f[u][0];
            f[u][0]=f[j][0]+w[i];
        }
        else if(f[u][1]<f[j][0]+w[i]) f[u][1]=f[j][0]+w[i];
    }
}

void dp2(int u,int fa,LL c)
{
    if(f[fa][0]!=f[u][0]+c)
    {
        if(f[u][0]<f[fa][0]+c)
        {
            f[u][1]=f[u][0];
            f[u][0]=f[fa][0]+c;
        }
        else if(f[u][1]<f[fa][0]+c) f[u][1]=f[fa][0]+c;
    }
    else
    {
        if(f[u][0]<f[fa][1]+c)
        {
            f[u][1]=f[u][0];
            f[u][0]=f[fa][1]+c;
        }
        else if(f[u][1]<f[fa][1]+c) f[u][1]=f[fa][1]+c;
    }

    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(j==fa) continue;
        dp2(j,u,w[i]);
    }
}

int main()
{
    while(scanf("%d",&n)!=-1)
    {
        memset(h,-1,sizeof h);
        idx=0;
        for(int i=2;i<=n;i++)
        {
            int fa;
            LL w;
            scanf("%d%lld",&fa,&w);
            add(fa,i,w);
        }

        dp1(1,-1);
        for(int i=h[1];i!=-1;i=ne[i]) dp2(e[i],1,w[i]);
        for(int i=1;i<=n;i++) printf("%d\n",f[i][0]);
    }

    return 0;
}
  • $1.4.2$ 树形DP与背包问题结合
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=310;
int n,m,num;
int h[N],e[N],w[N],ne[N],idx=0;
int f[N][N],sizes[N],dfn[N];

void add(int a,int b,int c)
{
    e[++idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx;
}

void dfs(int u)
{
    sizes[u]=1;
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        dfs(j);
        sizes[u]+=sizes[j];
    }
    dfn[++num]=u;
}

int main()
{
    memset(h,-1,sizeof h);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        int a,w;
        scanf("%d%d",&a,&w);
        add(a,i,w);
    }

    dfs(0);
    for(int i=1;i<=n+1;i++)
    for(int j=min(m+1,i);j>=1;j--)
        f[i][j]=max(f[i-sizes[dfn[i]]][j],f[i-1][j-1]+w[dfn[i]]);
    printf("%d\n",f[n+1][m+1]);
    return 0;
}

$1.6$ 单调队列优化DP

  • $1.6.1$ 围栏
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=30500;
int n,m;
LL dp[N];

struct node
{
    int l,v,s;
    bool operator < (const node& g) const
    {
        return s<g.s;
    }
}p[N];

int main()
{
    scanf("%d%d",&n,&m);
    for(int k=1;k<=m;k++) scanf("%d%d%d",&p[k].l,&p[k].v,&p[k].s);
    sort(p+1,p+1+m);

    for(int k=1;k<=m;k++)
    {
        int s=p[k].s,v=p[k].v,l=p[k].l;
        int mn=max(0,s-l);
        int mx=min(n,s+l-1);
        LL x[N],q[N],t[N],st=1,ed=0;

        for(int i=mn;i<=mx;i++) x[i]=dp[i]-i*v;
        for(int i=mn;i<s;i++)
        {
            while(st<=ed&&q[ed]<=x[i]) ed--;
            q[++ed]=x[i];
            t[ed]=i;
        }

        for(int i=s;i<=mx;i++)
        {
            while(st<=ed&&t[st]<i-l) st++;
            if(st>ed) break;
            dp[i]=max(dp[i],q[st]+v*i);
        }
        for(int i=2;i<=n;i++) dp[i]=max(dp[i],dp[i-1]);
    }

    printf("%lld\n",dp[n]);
    return 0;
}
  • $1.6.2$ 跳房子
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=5e5+10;
ll n,d,k,s[N],w[N],f[N];

bool check(int m)
{
    ll l=d-m,r=d+m;
    if(l<1) l=1;
    memset(f,-0x3f,sizeof f);
    f[0]=0;
    for(int i=1;i<=n;i++)
    for(int j=i-1;j>=0;j--)
    {
        if(s[i]-s[j]<l) continue;
        if(s[i]-s[j]>r) break;
        f[i]=max(f[i],f[j]+w[i]);
        if(f[i]>=k) return 1;
    }
    return 0;
}

int main()
{
    scanf("%lld%lld%lld",&n,&d,&k);
    for(int i=1;i<=n;i++)
    scanf("%lld%lld",&s[i],&w[i]);
    ll l=0,r=2e4+10,ans=-1;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(check(mid)) ans=mid,r=mid-1;
        else l=mid+1;
    }
    printf("%lld\n",ans);
    return 0;
}

0 评论