DP——由蒟蒻到神犇的进阶之路

开始更新咯

DP专题【题目来源BZOJ】

一、树形DP

1.bzoj2286消耗战

题解：因为是树形结构，一个点与根节点不联通，删一条边即可，

　　　于是我们就可以简化这棵树，把有用的信息建立一颗虚树，然后开始DP即可

 /*
 思路：
 */
 #include<algorithm>
 #include<cstdio>
 #include<cmath>
 #include<iostream>
 #include<cstring>
 #define ll long long
 #define inf 1e60
 #define N 250005
 #define M 550005
 using namespace std;
 int n,m,k,tot,top,tmp,ind;
 int a[N];
 int now[N],pre[M],v[M],val[M];
 int now1[N],pre1[M],v1[M];
 int fa[N][],deep[N],dfn[N],bin[];
 int z[M],st[M];
 ll f[N],mx[N];
 int read()
 {
     int x=,f=; char ch;
     while (ch=getchar(),ch<''||ch>'') if (ch=='-') f=-;
     while (x=x*+ch-'',ch=getchar(),ch>=''&&ch<='');
     return x*f;
 }
 void ins(int a,int b,int c){
     ++tot; pre[tot]=now[a]; now[a]=tot; v[tot]=b; val[tot]=c;
 }
 void insert(int a,int b){
     if (a==b) return;
     ++tot; pre1[tot]=now1[a]; now1[a]=tot; v1[tot]=b;
 }
 void dfs(int x)
 {
     dfn[x]=++ind;
     for (int i=; bin[i]<=deep[x]; i++)
         fa[x][i]=fa[fa[x][i-]][i-];
     for (int p=now[x]; p; p=pre[p])
     {
         int son=v[p];
         if (son==fa[x][]) continue;
         deep[son]=deep[x]+;
         mx[son]=min(mx[x],(ll)val[p]);
         fa[son][]=x;
         dfs(son);
     }
 }
 int lca(int x,int y)
 {
     if(deep[x]<deep[y]) swap(x,y);
     int t=deep[x]-deep[y];
     for (int i=; bin[i]<=t; i++)
     if (bin[i]&t) x=fa[x][i];
     for (int i=; i>=; i--)
         if (fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
     if (x==y) return x; return fa[x][];
 }
 void prework()
 {
     bin[]=;
     for (int i=; i<=; i++) bin[i]=bin[i-]*;
      tmp=; mx[]=inf; dfs();
 }
 bool cmp(int a,int b){return dfn[a]<dfn[b];
 }
 void work()
 {
     sort(a+,a+k+,cmp);
     top=tot=;
     z[]=a[]; top++;
     for (int i=; i<=k; i++) if (lca(z[top],a[i])!=z[top]) z[++top]=a[i];
     st[]=; tmp=;
     for (int i=; i<=top; i++)
     {
         int now=z[i],f=lca(now,st[tmp]);
         for (;;)
         {
             if (deep[f]>=deep[st[tmp-]])
             {
                 insert(f,st[tmp--]);
                 if (st[tmp]!=f) st[++tmp]=f;
                 break;
             }
             insert(st[tmp-],st[tmp]); tmp--;
         }
         if (st[tmp]!=now) st[++tmp]=now;
      }
      while (--tmp) insert(st[tmp],st[tmp+]);
 }
 void dp(int x)
 {
     f[x]=mx[x]; ll sum=;
     for (int p=now1[x]; p; p=pre1[p])
     {
         int son=v1[p]; dp(son); sum+=f[son];
     }
     now1[x]=;
     if (sum==) f[x]=mx[x]; else f[x]=min(f[x],sum);
 }
 void init()
 {
     n=read();
     for (int i=; i<n; i++)
     {
         int u=read(),v=read(),val=read();
         ins(u,v,val); ins(v,u,val);
     }
 //    m=read();
     prework();
 }
 void solve()
 {
     m=read();
     for (int i=; i<=m; i++)
     {
         k=read(); for (int j=; j<=k; j++) a[j]=read(); work();
         dp(); printf("%lld\n",f[]);
     }
 }
 int main()
 {
     init();
     solve();
     return ;
 }

2.bzoj1827奶牛大集会

题解：树形DP，先以1号点为根节点，然后再次树形DP求出其他节点为根的答案即可

 #include<algorithm>
 #include<iostream>
 #include<cstring>
 #include<cmath>
 #include<cstdio>
 #define ll long long
 #define inf 1e60
 #define N  200005
 #define M  500005
 using namespace std;
 int n,m;
 int now[N],pre[M],v[M],val[M],tot;
 ll f[N];
 int size[N],num[N],dis[N];
 ll ans,sum;
 void ins(int a,int b,int c)
 {
     ++tot; pre[tot]=now[a]; now[a]=tot; v[tot]=b; val[tot]=c;
 }
 int read()
 {
     int x=,f=; char ch;
     while (ch=getchar(),ch<''||ch>'') if (ch=='-') f=-;
     while (x=x*+ch-'',ch=getchar(),ch>=''&&ch<='');
     return x*f;
 }
 void init()
 {
     n=read();
     for (int i=; i<=n; i++) num[i]=read(),sum+=num[i];
     for (int i=; i<n; i++)
     {
         int u=read(),v=read(),val=read();
         ins(u,v,val); ins(v,u,val);
     }
 }
 void dfs(int x,int fa)
 {
     size[x]=num[x];
     for (int p=now[x]; p; p=pre[p])
     {
         int son=v[p];
         if (son==fa) continue;
         dis[son]=dis[x]+val[p];
         f[son]=1ll*dis[son]*num[son];
         dfs(son,x);
         size[x]+=size[son];
         f[x]+=f[son];
     }
 }
 void treedp(int x,int fa)
 {
     for (int p=now[x]; p; p=pre[p])
     {
         int son=v[p];
         if (son==fa) continue;
         f[son]=f[x]-1ll*size[son]*val[p]+1ll*(sum-size[son])*val[p];
         treedp(son,x);
     }
 }
 void solve()
 {
     dfs(,);
     //cout<<" "<<sum<<endl;
     treedp(,);
     ans=inf;
     for (int i=; i<=n; i++) ans=min(ans,f[i]);
     printf("%lld\n",ans);
 }
 int main()
 {
     init();
     solve();
 }
 /*

 */

3.bzoj1596电话网络

题解：树形DP，f[i][1]代表以i为根的子树都被覆盖的代价且在i放，[0]为都被覆盖i不放，

　　　[2]为子树被覆盖，i没被覆盖的代价

　　　f[i][1]=min(f[son][0],f[son][1],f[son][2])+1;

　　　f[i][0]=最小的f[son][1]+min(f[son][0],f[son][1]);

　　　f[x][2]+=f[son][0];

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#define ll long long
#define inf 100000000
#define N  10005
#define M  30005
using namespace std;
int n;
int pre[M],v[M],now[N],tot;
int f[N][];
void ins(int a,int b){++tot; pre[tot]=now[a]; now[a]=tot; v[tot]=b;
}
int read()
{
    int x=,f=; char ch;
    while (ch=getchar(),ch<''||ch>'') if (ch=='-') f=-;
    while (x=x*+ch-'',ch=getchar(),ch>=''&&ch<='');
    return x*f;
}
void dfs(int x,int fa)
{
    int sum=;
    f[x][]=; f[x][]=inf;
    for (int p=now[x]; p; p=pre[p])
    {
        int son=v[p];
        if (son==fa) continue;
        dfs(son,x);
        f[x][]+=min(f[son][],min(f[son][],f[son][]));
        f[x][]+=f[son][];
    }
    for (int p=now[x]; p; p=pre[p])
    {
        int son=v[p]; if (son==fa) continue;
        int who=son; sum=f[son][];
        for (int j=now[x]; j; j=pre[j]) if ((v[j]!=fa) && (v[j]!=who)) sum+=min(f[v[j]][],f[v[j]][]);
        f[x][]=min(f[x][],sum);
    }
}
int main()
{
    n=read();
    for (int i=; i<n; i++)
    {
        int u=read(),v=read();
        ins(u,v); ins(v,u);
    }
    dfs(,);
    printf("%d\n",min(f[][],f[][]));
}

4.bzoj1864三色二叉树

题解：f[i][0]代表i为绿色的答案，f[i][1]为i为其他颜色的答案

　　　f[i][0]=max(f[ls[i]][0]+f[rs[i]][1],f[ls[i]][1]+f[rs[i]][0]);

　　　f[i][1]=f[ls[i]][0]+f[rs[i]][1]+1;

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdio>
#define ll long long
#define inf 1000000000
#define N 300005
using namespace std;
int ls[N],rs[N];
int n,m,size,ans1,ans2;
int f[N][];
void read(int x)
{
    char ch=getchar();
    if (ch=='') return;
    if (ch=='') ls[x]=++size,read(ls[x]);
    if (ch=='') ls[x]=++size,read(ls[x]),rs[x]=++size,read(rs[x]);
}
void dp1(int x)
{
    if (!x) return ;
    dp1(ls[x]); dp1(rs[x]);
    f[x][]=f[ls[x]][]+f[rs[x]][]+;
    f[x][]=max(f[ls[x]][]+f[rs[x]][],f[ls[x]][]+f[rs[x]][]);
}
void dp2(int x)
{
    if (!x) return;
    dp2(ls[x]); dp2(rs[x]);
    f[x][]=f[ls[x]][]+f[rs[x]][]+;
    f[x][]=min(f[ls[x]][]+f[rs[x]][],f[ls[x]][]+f[rs[x]][]);
}
void solve()
{
    dp1(); ans1=max(f[][],f[][]);
    memset(f,,sizeof(f));
    dp2(); ans2=min(f[][],f[][]);
    printf("%d %d\n",ans1,ans2);
}
int main()
{
    read(++size);
    solve();
}

5.bzoj1060时态同步

题解：f[i]代表以i为子树的儿子时间同步所需长度

　　　ans+=maxsonf-(f[son]+val[p])

　　　:val[p]为边权，maxsonf为i为子树的最长的长度

#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#define ll long long
#define inf 0x7ffffff
#define N 500005
#define M 1000005
using namespace std;
int now[N],pre[M],v[M],val[M],f[N];
int n,m,s,tot;
ll ans;
int read()
{
    int x=,f=; char ch;
    while (ch=getchar(),ch<''||ch>'') if (ch=='-') f=-;
    while (x=x*+ch-'',ch=getchar(),ch>=''&&ch<='');
    return x*f;
}
void ins(int a,int b,int c)
{
    ++tot; pre[tot]=now[a]; now[a]=tot; v[tot]=b; val[tot]=c;
}
void work(int x,int fa)
{
    for (int p=now[x]; p; p=pre[p])
    {
        int son=v[p];
        if (son==fa) continue;
        work(son,x);
        f[x]=max(f[x],f[son]+val[p]);
    }
    for (int p=now[x]; p; p=pre[p])
    {
        int son=v[p];
        if (son==fa) continue;
        ans+=f[x]-(f[son]+val[p]);
    }
}
int main()
{
    n=read();
    s=read();
    for (int i=; i<n; i++)
    {
        int u=read(),v=read(),val=read();
        ins(u,v,val); ins(v,u,val);
    }
    work(s,); printf("%lld\n",ans);
}

6.bzoj2435道路修建

题解：ans+=val[p]*size[i]*(n-size[i])  size[i]为i为根的子树大小

#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#define ll long long
#define inf 0x7ffffff
#define N 1000005
#define M 2000005
using namespace std;
int now[N],pre[M],v[M],val[M],size[N];
int n,tot;
ll ans;

int read()
{
    int x=,f=; char ch;
    while (ch=getchar(),ch<''||ch>'') if (ch=='-') f=-;
    while (x=x*+ch-'',ch=getchar(),ch>=''&&ch<='');
    return x*f;
}
void ins(int a,int b,int c)
{
    ++tot; pre[tot]=now[a]; now[a]=tot; v[tot]=b; val[tot]=c;
}
void dfs(int x,int fa)
{
    size[x]=;
    for (int p=now[x]; p; p=pre[p])
    {
        int son=v[p];
        if (son==fa) continue;
        dfs(son,x); size[x]+=size[son];
        ans+=1ll*val[p]*(abs(n-size[son]-size[son]));
    }
}
int main()
{
    n=read();
    for (int i=; i<n; i++)
    {
        int u=read(),v=read(),val=read();
        ins(u,v,val); ins(v,u,val);
    }
    dfs(,);
    printf("%lld\n",ans);
}

7.bzoj2427软件安装

题解：缩点+反边+dp【详见代码】

#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#define ll long long
#define inf 2000000000000
#define N 205
#define M 605
using namespace std;
int n,m;
int cost[N],val[N],depend[N],belong[N];
struct data{
    int tot,pre[M],now[N],v[M];
}a,b;
int tot,dfn[N],low[N],z[N],id;
bool vis[N],in[N];
int sc[N],sv[N],type;
int f[N][M];
int read()
{
    int x=,f=; char ch;
    while (ch=getchar(),ch<''||ch>'') if (ch=='-') f=-;
    while (x=x*+ch-'',ch=getchar(),ch>=''&&ch<='');
    return x*f;
}
void ins1(int u,int v)
{
//    cout<<" "<<u<<" "<<v<<endl;
    ++a.tot; a.pre[a.tot]=a.now[u]; a.now[u]=a.tot; a.v[a.tot]=v;
}
void ins2(int u,int v)
{
    //cout<<" "<<u<<" "<<v<<endl;
    ++b.tot; b.pre[b.tot]=b.now[u]; b.now[u]=b.tot; b.v[b.tot]=v;
}
void tarjan(int x){
    int son=;
    dfn[x]=low[x]=++id;
    z[++tot]=x; vis[x]=true;
    for (int p=a.now[x]; p; p=a.pre[p])
    {
        son=a.v[p];
        if (!dfn[son])
        {
            tarjan(son); low[x]=min(low[x],low[son]);
        } else if (vis[son]) low[x]=min(low[x],dfn[son]);
    }
    if (low[x]==dfn[x])
    {
        ++type;
        while (son!=x)
        {
            son=z[tot--]; vis[son]=false; belong[son]=type;
            sv[type]+=val[son]; sc[type]+=cost[son];
        }
    }
}
void init_pre()
{
    n=read(); m=read();
    for (int i=; i<=n; i++) cost[i]=read();
    for (int i=; i<=n; i++) val[i]=read();
    for (int i=; i<=n; i++)
    {
        int x=read();
        if(x)ins1(x,i);
    }
    for (int i=; i<=n; i++)
    {
        if (!dfn[i]) tarjan(i);
    }
    for (int i=; i<=n; i++)
    {
        for (int p=a.now[i]; p; p=a.pre[p])
        {
            int son=a.v[p];
            if (belong[son]!=belong[i]) ins2(belong[i],belong[son]),in[belong[son]]=true;
        }
    }
    for (int i=; i<=type; i++)
    {
        if (!in[i]) ins2(type+,i);
    }
    type++;
}
void dp(int x)
{
    for (int p=b.now[x]; p; p=b.pre[p])
    {
        int son=b.v[p];
        dp(son);
        for (int j=m-sc[x]; j>=; j--)
            for (int k=; k<=j; k++) f[x][j]=max(f[x][j],f[x][j-k]+f[son][k]);
    }
    for (int j=m; j>=; j--)
    {
        if (j>=sc[x]) f[x][j]=f[x][j-sc[x]]+sv[x]; else f[x][j]=;
    }
}
void solve()
{
    dp(type);
    printf("%d\n",f[type][m]);
}
int main()
{
    init_pre();
    solve();
}

8.bzoj1369GEM

题解：开始智障了，以为只有整棵树为1或2的情况，于是GG了，实践证明数值个数不会超过5.

#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#define ll long long
#define inf 0x7ffffff
#define N 10005
#define M 20005
using namespace std;
int n,m,tot;
int pre[M],v[M],now[N];
int f[N][];
int read()
{
    int x=,f=; char ch;
    while (ch=getchar(),ch<''||ch>'') if (ch=='-') f=-;
    while (x=x*+ch-'',ch=getchar(),ch>=''&&ch<='');
    return x*f;
}
void ins(int a,int b) {++tot; pre[tot]=now[a]; now[a]=tot; v[tot]=b;
}
void dp(int x,int fa)
{
    for (int i=; i<=; i++) f[x][i]=i;
    for (int p=now[x]; p; p=pre[p])
    {
        int son=v[p];
        if (son==fa) continue;
        dp(son,x);
    }
    for (int i=; i<=; i++)
    {
        for (int p=now[x]; p; p=pre[p])
        {
            int son=v[p]; if (son==fa) continue; int sum=inf;
            for (int j=; j<=; j++)
            {
                if (j==i) continue;
                sum=min(sum,f[son][j]);
            }
            f[x][i]+=sum;
        }
    }
}
void solve()
{
    dp(,); int ans=inf;
    for (int i=; i<=; i++) ans=min(ans,f[][i]); printf("%d\n",ans);

}
int main()
{
    n=read();
    for (int i=; i<n; i++)
    {
        int u=read(),v=read(); ins(u,v); ins(v,u);
    }
    solve();
}

9.bzoj3573米特运输

题解：可以发现一个特点，当我们确定一个点的时候，整棵树都可以确定，于是我们枚举留下留哪一个点且记录根的值，n-一样的 即为答案

#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#define ll long long
#define inf 0x7ffffff
#define N 500005
#define M 1000005
using namespace std;
int n;
int pre[M],v[M],now[N],a[N];
double s[N],val[N];
int in[N];
int tot,tmp,ans;
int read()
{
    int x=,f=; char ch;
    while (ch=getchar(),ch<''||ch>'') if (ch=='-') f=-;
    while (x=x*+ch-'',ch=getchar(),ch>=''&&ch<='');
    return x*f;
}
void ins(int a,int b)
{
    ++tot; pre[tot]=now[a]; now[a]=tot; v[tot]=b;
}
void dp(int x,int fa)
{
    for (int p=now[x]; p; p=pre[p])
    {
        int son=v[p];
        if (son==fa) continue;
        s[son]=s[x]+log(in[x]);
        dp(son,x);
    }
}
int main()
{
    n=read();
    for (int i=; i<=n; i++) a[i]=read();
    for (int i=; i<n; i++)
    {
        int u=read(),v=read(); ins(u,v); ins(v,u);
        in[u]++; in[v]++;
    }
    for (int i=; i<=n; i++) in[i]--;
    s[]=log();
    dp(,);
    for (int i=; i<=n; i++)
    {
        val[i]=s[i]+log(a[i]);
    }
    sort(val+,val+n+); ans=n*; tmp=;
    for (int i=; i<=n; i++)
    {
        if (val[i]-val[i-]<1e-) tmp++;
        else tmp=;
        ans=min(ans,n-tmp);
    }

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

10.bzoj3522Hotel

题解：因为我没妹子所以就不屑于写这种题【虐狗啊】

　　　枚举节点，以这个节点为中心，于是我们只要知道到这个节点的距离为J的有多少，然后组合排列的转换，搞一搞就好了

#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#define ll long long
#define inf 0x7ffffff
#define N 5005
#define M 10005
using namespace std;
int pre[M],v[M],now[N];
int tmp[N],dis[N],s1[N],s2[N];
int tot,n,m,mx;
ll ans;
int read()
{
    int x=,f=; char ch;
    while (ch=getchar(),ch<''||ch>'') if (ch=='-') f=-;
    while (x=x*+ch-'',ch=getchar(),ch>=''&&ch<='');
    return x*f;
}
void ins(int a,int b){++tot; pre[tot]=now[a]; now[a]=tot; v[tot]=b;
}
void dp(int x,int fa)
{
    tmp[dis[x]]++; mx=max(mx,dis[x]);
    for (int p=now[x]; p; p=pre[p])
    {
        int son=v[p]; if (son==fa) continue;
        dis[son]=dis[x]+;
        dp(son,x);
    }
}
int main()
{
    n=read();
    for (int i=; i<n; i++)
    {
        int u=read(),v=read();
        ins(u,v); ins(v,u);
    }
    ans=;

    for (int i=; i<=n; i++)
    {
        memset(s1,,sizeof(s1));
        memset(s2,,sizeof(s2));
        for (int p=now[i]; p; p=pre[p])
        {
            int son=v[p];
            mx=dis[son]=; dp(son,i);
            for (int j=; j<=mx; j++)
            {
                ans+=s2[j]*tmp[j];
                s2[j]+=tmp[j]*s1[j];
                s1[j]+=tmp[j];
                tmp[j]=;
            }
        }
    }
    printf("%lld\n",ans);
}

小结：在树形DP过程中当我们不需要那些没有节点我们可以利用虚树来解决；

　　　 树形DP一般是在一棵树上的，且状态较多，贪心无法解决的问题；

　　　 树形DP一般可以看出，但是转移方程需要细想；

二、区间动规

1.bzoj1260涂色

题解：f[i][j]为i--j的涂色最小值

　　　f[i][j]=f[i+1][j]+a[i+1]==a[i]

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

　　　　　  =f[i+1][j-1](a[i]==a[j]==a[i+1]==a[j-1])

　　　　　  =f[i+1][j-1]+(a[i]==a[j]) [ a[i+1]!=a[i]||a[j]!=a[j-1] ]

　　　或者：a[i]==a[j]

　　　　　　则：f[i][j]=min(f[i+1][j],f[i][j-1])

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

#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#define ll long long
#define inf 0x7ffffff
#define N 100
using namespace std;
char s[N];
int f[N][N];
int n,ans;
void dp()
{
    for (int i=; i<=n; i++) for (int j=; j<=n; j++) f[i][j]=inf/;
    for (int i=; i<=n; i++) f[i][i]=;
    for (int len=; len<n; len++)
    {
        for (int i=; i<=n; i++)
        {
            int j=i+len;
            if (j>n) break;
            if (s[i]==s[j])
            {
                if (len==) f[i][j]=;
                else
                {
                    f[i][j]=min(f[i+][j],f[i][j-]);
                    f[i][j]=min(f[i][j],f[i+][j-]+);
                }
             }
             else
             {
                 for (int k=i; k<j; k++) f[i][j]=min(f[i][j],f[i][k]+f[k+][j]);
            }
        }
    }
}
int main()
{
    scanf("%s",s+);
    n=strlen(s+);
    dp();
    printf("%d\n",f[][n]);
}

2.bzoj1090字符串压缩

题解:f[i][j]---->i到j被压缩的最小长度；

　　 f[i][j]=min(f[i][k]+f[k+1][j]);

　　 same(i,j)代表i到j可以被压缩，【同下题解释】

　　 f[i][j]=i--j的最小段数的位数+2+i--j的最小段长；

　　 注：他们可以被压缩，但是我们不一定要全部压缩

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#define N 105
using namespace std;
char s[N];
int n;
bool mark[N][N];
int f[N][N];
bool same(int l,int r,int ll,int rr)
{
    if ((r-l+)%(rr-ll+)!=) return false ;
    int tmp=(rr-ll+);
    for (int i=l; i<=r; i++)
    {
        int tmp=rr-ll+;
        if (s[i]!=s[(i-l)%tmp+ll]) return false;
    }
    return true;
}
int get(int x)
{
    int t=;
    while (x) { x/=; t++;
    } return t;
}
int dp(int l,int r)
{
    int tmp=(r-l+);
    if (tmp==) return tmp;
    if (mark[l][r]) return f[l][r];
    mark[l][r]=;
    for (int i=l; i<r; i++)
    {
        tmp=min(tmp,dp(l,i)+dp(i+,r));
        if (same(i+,r,l,i)) tmp=min(tmp,dp(l,i)++get((r-i)/(i-l+)+));
    }
    return f[l][r]=tmp;
}
int main()
{
    scanf("%s",s+); n=strlen(s+);
    printf("%d\n",dp(,n));
}

3.bzoj1068压缩

题解：f[i][j][t]---->i到j的这一段中间插了（T==1) M的最小压缩长度；

　　　f[i][j][1]=min(f[i][k][1]+f[k+1][j][1]);

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

　　　same(i,j) f[i][j][t]=f[i][(i+j)/2][0]+1;

 /*
     f[i][j][t]---->i到j的这一段中间插了（T==1) M；
 */
 #include<algorithm>
 #include<cstdio>
 #include<cstring>
 #include<cmath>
 #define N 105
 using namespace std;
 int n;
 char s[N];
 int f[N][N][];
 bool mark[N][N][];
 bool same(int l,int r)
 {
     int tmp=r-l+;
     if (tmp&) return false;
     for (int i=l; i<=(l+r)/; i++)
     {
         if (s[i]!=s[i+tmp/]) return false;
     }
     return true;
 }
 int dp(int l,int r,int t)
 {
     int tmp=r-l+;
     if (tmp==) return ;
     if (mark[l][r][t]) return f[l][r][t];
     mark[l][r][t]=;
     if (t==) for (int i=l; i<r; i++) tmp=min(tmp,dp(l,i,)+dp(i+,r,)+);
     for (int i=l; i<r; i++) tmp=min(tmp,dp(l,i,t)+r-i);
     if (same(l,r)) tmp=min(tmp,dp(l,(l+r)/,)+);
     return  f[l][r][t]=tmp;
 }
 int main()
 {
     scanf("%s",s+);
     n=strlen(s+);
     printf("%d\n",dp(,n,));
 }

小结：区间DP一般处理区间覆盖、压缩之类问题，但是容易与数据结构弄混，

　　　导致代码长度大；

三、状压

/*

序：因为状压dp方式类似，

　　故具体方程不予列出，

　　细节详见代码；

*/

1.bzoj1725牧场的安排

题解：f[i][j]代表第i行状态为j的情况数；

　　　转移见代码；

#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#define ll long long
#define inf 0x7ffffff
#define N 13
#define M 4096
#define base 100000000
using namespace std;
int f[N][M],val[N];
int maxn,n,m,ans;
int read()
{
    int x=,f=; char ch;
    while (ch=getchar(),ch<''||ch>'') if (ch=='-') f=-;
    while (x=x*+ch-'',ch=getchar(),ch>=''&&ch<='');
    return x*f;
}
void dp()
{
    for (int i=; i<=maxn; i++)
    if((i&(i>>))==&&(i|val[])==val[])
        f[][i]=;//,cout<<"    "<<i<<endl;
    //    if (((i & (i>>1))==0) && (i|val[1])==val[1]) f[1][i]==1,cout<<" dd"<<endl;
    for (int i=; i<=n; i++)
    {
        for (int j=; j<=maxn; j++)
        {
            if (f[i-][j])
            for (int k=; k<=maxn; k++)
            {
                //if (((k&(k>>1))==0) && (k|val[i])==val[i] && (k&j)==0) f[i][k]=(f[i][k]+f[i-1][j])%base,cout<<" dd "<<endl;
                if((j&k)==&&(k|val[i])==val[i]&&(k&(k>>))==)
                    f[i][k]=(f[i][k]+f[i-][j])%base;
            }
        }
    }
}
int main()
{
    n=read(); m=read();
    for (int i=; i<=n; i++)
    {
        for (int j=; j<=m; j++)
        {
            int x=read();
            val[i]<<=; val[i]+=x;
        }
    }
    maxn=(<<m)-;
    dp();
    for (int i=; i<=maxn; i++)
    {
        ans=(ans+f[n][i])%base;
    }
    printf("%d\n",ans);
}

2.bzoj1087互不侵犯king

题解：同上，具体见代码；

#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#define ll long long
#define inf 0x7ffffff
#define N 10
#define M 525
#define KK 9*9+5
using namespace std;
int n,K,maxn;
ll ans;
ll f[N][M][KK];
int t[N],num[M];
bool bo[M],can[M][M];
int read()
{
    int x=,f=; char ch;
    while (ch=getchar(),ch<''||ch>'') if (ch=='-') f=-;
    while (x=x*+ch-'',ch=getchar(),ch>=''&&ch<='');
    return x*f;
}
void prework()
{
    t[]=; for (int i=; i<=n; i++) t[i]=t[i-]<<; maxn=(<<n)-;
    for (int i=; i<=maxn; i++)
    {
        if (i&(i>>)) continue;
        int x=;
        for (int j=; j<=n; j++) if (i & t[j]) x++;
        num[i]=x; bo[i]=;
    }
    for (int i=; i<=maxn; i++) if (bo[i])
        for (int j=; j<=maxn; j++) if (bo[j])
        {
            if ((i&j)== && ((i<<) & j)== && ((j<<) & i)==) can[i][j]=;
        }
}
void dp()
{
    for (int i=; i<=maxn; i++) if (bo[i]) f[][i][num[i]]=;
    for (int i=; i<n; i++)
        for (int j=; j<=maxn; j++) if (bo[j])
            for (int k=; k<=maxn; k++) if (bo[k])
            if (can[j][k])
            {
                for (int p=num[j]; p+num[k]<=K; p++) f[i+][k][p+num[k]]+=f[i][j][p];
            }
}
int main()
{
    n=read(); K=read();
    prework();
    dp();
    for (int i=; i<=maxn; i++) ans+=f[n][i][K];
    printf("%lld\n",ans);
    return ;
}

3.bzoj1688疾病管理

题解：f[i]疾病状态为i的最大选取牛数

　　　j|val[k]==i;f[i]=max(f[j|val[k]]+1);

　　　注：val[k]为第k头牛的疾病状态；

#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#define ll long long
#define inf 0x7ffffff
#define M    42768
using namespace std;
int n,d,k,maxn;
int f[M],val[M];
int read()
{
    int x=,f=; char ch;
    while (ch=getchar(),ch<''||ch>'') if (ch=='-') f=-;
    while (x=x*+ch-'',ch=getchar(),ch>=''&&ch<='');
    return x*f;
}
bool check(int x)
{
    int cnt=;
    while (x) { cnt+=x&; x>>=;
    }
    return cnt<=k;
}
int main()
{
    n=read(); d=read(); k=read();
    for (int i=; i<=n; i++)
    {
        int x=read(),a;
        while (x--) a=read(),val[i]|=(<<(a-));
    }
    maxn=(<<d)-;
    for (int i=; i<=n; i++)
        for (int j=maxn; j; j--) f[j|val[i]]=max(f[j|val[i]],f[j]+);
    int ans=;
    for (int i=; i<=maxn; i++) if (check(i)) ans=max(ans,f[i]); printf("%d\n",ans);
}
/*
6 3 2
0
1 1
1 2
1 3
2 2 1
2 2 1
*/

4.bzoj2073PRZ

题解：f[i]为状态为i，本次选择重量为j的最小时间

　　　sc[j]<M; f[i]=min(f[i],f[j^i]+sw[j]);

　　　sc[j],sw[j]分别为状态为j的重量与时间

#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#define ll long long
#define inf 0x7ffffff
#define N 20
#define M 70000
using namespace std;
int W,n,maxn;
int f[M],st[M],sw[M];
int t[N],w[N];
int read()
{
    int x=,f=; char ch;
    while (ch=getchar(),ch<''||ch>'') if (ch=='-') f=-;
    while (x=x*+ch-'',ch=getchar(),ch>=''&&ch<='');
    return x*f;
}
/*
    颓废死亡与坚持成功，请自己选择；
*/
void prework()
{
    maxn=(<<n)-;
    for (int i=; i<=maxn; i++)
    {
        int x=i,z=;
        while (x)
        {
            if (x&) sw[i]+=w[z],st[i]=max(st[i],t[z]);
            x>>=; z++;
        }
    }
}
void dp()
{
    f[]=;
    for (int i=; i<=maxn; i++)
    {
        f[i]=inf/;
        for (int j=i; j; j=i&(j-)) if (sw[j]<=W)
        f[i]=min(f[i],f[i^j]+st[j]);
    }
}
int main()
{
    W=read(); n=read();
    for (int i=; i<=n; i++)
    {
        t[i]=read(); w[i]=read();
    }
    prework();
    dp();
    printf("%d\n",f[maxn]);
}

5.bzoj1231混乱的奶牛

题解：f[i][j]为状态为i，末尾奶牛为j的答案；

　　　详见代码；

#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#define ll long long
#define inf 0x7ffffff
#define N 17
#define M 70000
using namespace std;
int n,m,maxn;
int s[N],bin[N];
ll f[M][N],ans;
int read()
{
    int x=,f=; char ch;
    while (ch=getchar(),ch<''||ch>'') if (ch=='-') f=-;
    while (x=x*+ch-'',ch=getchar(),ch>=''&&ch<='');
    return x*f;
}
/*
    颓废死亡与坚持成功，请自己选择；
*/
int main()
{
    n=read(); m=read();
    for (int i=; i<=n; i++) s[i]=read();
    bin[]=; for (int i=; i<=n; i++) bin[i]=bin[i-]<<;
    for (int i=; i<=n; i++) f[bin[i]][i]=;
    maxn=(<<n)-;
    for (int i=; i<=maxn; i++)
    {
        for (int j=; j<=n; j++) if (i&bin[j])
        for (int k=; k<=n; k++) if ((bin[k]|i)!=i && abs(s[j]-s[k])>m)
        f[bin[k]|i][k]+=f[i][j];
    }
    for (int i=; i<=n; i++) ans+=f[maxn][i];
    printf("%lld\n",ans);
}

6.bzoj1072排列

题解：f[i][j]状态为i 余数为 j的状态数

　　　f[i|bin[k-1]][(j*10+a[k])%d]+=f[i][j]

　　　最后排列组合去重；

#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#define ll long long
#define inf 0x7ffffff

using namespace std;
int bin[];
int Case,d,len,maxn;
int a[],v[],tot[],f[][];
char s[];
int read()
{
    int x=,f=; char ch;
    while (ch=getchar(),ch<''||ch>'') if (ch=='-') f=-;
    while (x=x*+ch-'',ch=getchar(),ch>=''&&ch<='');
    return x*f;
}
/*
    颓废死亡与坚持成功，请自己选择；
*/
int main()
{
    Case=read();
    bin[]=;for(int i=;i<;i++)bin[i]=bin[i-]<<;
    while (Case--)
    {
        scanf("%s",s+); d=read();
        len=strlen(s+);
        for (int i=; i<=; i++) v[i]=,tot[i]=;
        for (int i=; i<=len; i++)
        {
            a[i]=s[i]-''; tot[a[i]]++; v[a[i]]*=tot[a[i]];
        }
        for (int i=; i<bin[len]; i++)
            for (int j=; j<d; j++) f[i][j]=;
        f[][]=;
        for(int i=;i<bin[len];i++)
        for(int k=;k<d;k++)
            if(f[i][k])
                for(int x=;x<=len;x++)
                    if((bin[x-]&i)==)
                        f[i|bin[x-]][(a[x]+k*)%d]+=f[i][k];
        for (int i=; i<=; i++) f[bin[len]-][]/=v[i];
        printf("%d\n",f[bin[len]-][]);
    }
}

小结：一般看到数据在20左右，就马上要想到状压DP；

四、斜率优化

1.bzoj1911特别行动队

题解：

待更------------------------