【DP专题】

区间DP

[USACO06FEB]奶牛零食Treats for the Cows

$$f[l][r]=max(f[l][r-1]+v[r] \times tp,f[l+1][r]+v[l] \times tp)$$

#include"cstdio"
#include"cstring"
#include"iostream"
#include"algorithm"
using namespace std;

const int MAXN=2005;

int n;
int v[MAXN];
int f[MAXN][MAXN];

int dfs(int tp,int l,int r)
{
    if(f[l][r]) return f[l][r]; 
    if(l==r) return f[l][r]=v[l]*tp;
    return f[l][r]=max(dfs(tp+1,l,r-1)+v[r]*tp,dfs(tp+1,l+1,r)+v[l]*tp);
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%d",&v[i]);
    printf("%d\n",dfs(1,1,n));
    return 0;
}

$$f[siz][x]=max(f[siz-1][x]+v[x+siz-1] \times (n-siz+1),f[siz-1][x+1]+v[x] \times (n-siz+1))$$

#include"cstdio"
#include"cstring"
#include"iostream"
#include"algorithm"
using namespace std;

const int MAXN=2005;

int n;
int v[MAXN];
int f[2][MAXN];

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%d",&v[i]);
    for(int i=1;i<=n;++i){
        for(int j=1;j+i-1<=n;++j){
            f[i&1][j]=max(f[i&1^1][j]+v[j+i-1]*(n-i+1),f[i&1^1][j+1]+v[j]*(n-i+1));
        }
    }printf("%d\n",f[n&1][1]);
    return 0;
}

LIS

魔族密码

$$f[i]=max(f[j])+1,(j \lt i) \land check(j)$$

#include"cstdio"
#include"cstring"
#include"iostream"
#include"algorithm"
using namespace std;

const int MAXN=2005;

int n,ans;
char ch[MAXN][85];
int f[MAXN];

bool check(int x,int y)
{
    int ln=strlen(ch[x]);
    for(int i=0;i<ln;++i) if(ch[x][i]!=ch[y][i]) return 0;
    return 1;
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%s",ch[i]);
        for(int j=1;j<i;++j) if(check(j,i)) f[i]=max(f[i],f[j]);
        ++f[i];ans=max(ans,f[i]);
    }printf("%d\n",ans);
    return 0;
}

背包

找啊找啊找GF

$$f[i][j]=min(f[i][j],f[i-w1[id]][j-w2[id]]+t[id]),g[i][j]==g[i-w1[id]][j-w2[id]]+1$$
$$f[i][j]=f[i-w1[id]][j-w2[id]]+t[id],g[i][j] \lt g[i-w1[id]][j-w2[id]]+1$$

#include"cstdio"
#include"cstring"
#include"iostream"
#include"algorithm"
#include"bitset"
using namespace std;

const int MAXN=105;

int n,m,r;
int w1[MAXN],w2[MAXN],v[MAXN];
int fn[MAXN][MAXN],ft[MAXN][MAXN];

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%d%d%d",&w1[i],&w2[i],&v[i]);
    scanf("%d%d",&m,&r);
    for(int i=1;i<=n;++i){
        for(int j=m;j>=w1[i];--j){
            for(int k=r;k>=w2[i];--k){
                if(fn[j][k]<fn[j-w1[i]][k-w2[i]]+1){
                    fn[j][k]=fn[j-w1[i]][k-w2[i]]+1;
                    ft[j][k]=ft[j-w1[i]][k-w2[i]]+v[i];
                }else if(fn[j][k]==fn[j-w1[i]][k-w2[i]]+1){
                    ft[j][k]=min(ft[j][k],ft[j-w1[i]][k-w2[i]]+v[i]);
                }
            }
        }
    }printf("%d\n",ft[m][r]);
    return 0;
}

[HAOI2012]音量调节

$$f[i][j-w[i]]|=f[i][j],j \ge w[i]$$
$$f[i][j+w[i]]|=f[i][j],j+w[i] \le maxn$$

#include"cstdio"
#include"cstring"
#include"iostream"
#include"algorithm"
using namespace std;

const int MAXN=1005;

int n,st,mx;
int a[55];
bool f[2][MAXN];

int main()
{
    scanf("%d%d%d",&n,&st,&mx);f[0][st]=1;
    for(int i=1;i<=n;++i) scanf("%d",&a[i]);
    for(int i=1;i<=n;++i){
        bool fl=0;memset(f[i&1],0,sizeof(f[i&1]));
        for(int j=mx;j>=a[i];--j) if(f[i&1^1][j-a[i]]) f[i&1][j]=fl=1;
        for(int j=0;j<=mx-a[i];++j) if(f[i&1^1][j+a[i]]) f[i&1][j]=fl=1;
        if(!fl){puts("-1");return 0;}
    }for(int i=mx;i>=0;--i) if(f[n&1][i]){printf("%d\n",i);return 0;}
    return 0;
}