动态规划

• 线型动态规划
• 资源分配类动态规划
• 树形动态规划
• 区间与环形动态规划
• 状态压缩型动态规划

线型动态规划

几个典型模版：

• LIS 最长上升子序列

• LCS最长公共子序列

LIS最长上升子序列

求一个序列中最长的单调上升的子序列长度

子序列定义：简称子列，某个序列的子序列是从最初序列通过去除某些元素但不破坏余下元素的相对位置（在前或在后）而形成的新序列。

设$f[i]$表示以$f[i]$结尾的最长上升子序列的长度

【状态转移方程】$f[i]=max\{f[j]+1\}$满足$1\leq j<i\leq 且 有a[j]<a[i]$

【时间复杂度】$O(n^2)$

优化:

设$f[i]$表示到i位置时，最长上升子序列的末尾最小元素是什么

【状态转移方程】

$\qquad f[i]=\begin{cases} f[++len]=a[i]\qquad (a[i]>f[len])\\ f[j]=a[i]\qquad \qquad\ \ \ \ (a[i]<=f[len],f[j]是第一个大于或者等于a[i]的数)\end{cases}$

【时间复杂度】 $nlogn$

lower_bound维护第二个操作

例题：

【合唱队形】

正反两次的最长上升子序列

【导弹拦截】

求一个最长不升子序列的长度和一个最长上升子序列的长度

【木棍加工】

考虑到一个木棍有两个性质，当满足两维都单调下降的时候，不用准备时间

此时需要dilworth定理：

下降子序列的最小划分等于最长不下降子序列的长度

我们将第一维排序，第二维跑最长不下降子序列

LCS最长公共子序列

求给定的两个x,y序列中的最长公共子序列的长度

$x$长度位$n$,$y$长度为$m$

设$f[i][j]$表示$x$的前$i$位与$y$的前$j$位的最长公共子序列的长度

【状态转移方程】

$f[i][j]=\begin{cases}max\{ f[i-1[j],f[i][j-1]\}\qquad\ (x[i]\neq y[j])\\ f[i-1][j-1]+1\qquad\qquad\qquad (x[i]=y[i] )\end{cases}$

【时间复杂度】$O(n*m)$

例题：

【最长公共子序列】

由于题目性质，考虑离散化的思路将此题转化为LCS

【编辑距离】

设$f[i][j]$表示将$x$的前$i$位变为y的前$j$位最少需要的步数

【状态转移方程】

$f[i][j]=\begin{cases}min(f[i-1[j],f[i][j-1],f[i-1][j-1])+1(f[i]\ne f[j])\\f[i-1][j-1]\end{cases}$

当$f[i]\ne f[j]$ 时：$f[i-1][j]$表示删除操作，$f[i][j-1]$表示插入操作，$f[i][j]$表示替换操作

例题

【尼克的任务】

设$f[i]$ 表示从$i-n$的最大空闲时间**

【状态转移方程】$f[i]=max(f[i],f[i-sum[i]])$

表示当前i号任务完成所需要的时间

【加分二叉树】

设$f[i][j]$表示区间$i-j$建成一棵树的最大分数

【状态转移方程】 $f[i][j]=max\{f[i][k-1]\times f[k+1][j]+f[k][k]\}$

记录$root[i][j]$表示区间$i-j$建成树时最大分数所取的根节点，枚举k即可

【大师】

设$f[i][j]$表示以第$i$个数结尾的公差为$j$的方案数

【状态转移方程】 $f[i][j]=（f[i][a[i]-a[j]]+f[j][a[i]-a[j]]+1)\%mod$

考虑到有可能出现公差为负数，所以二维加上一个$a[i]$最大值

【摆花】

设$f[i][j]$表示当摆完第$i$种花时，已经摆了$j$盆的方案数

考虑到数组过大，可以用滚动数组优化空间

枚举第三维状态的时候倒着枚举，可以优化掉第三维

【状态转移方程】 $f[i][j]=\sum_{k=max(j-a[i],0)}^{j}f[i-1][k]$

【Golden Sword】

设$f[i][j]$表示放进$i$种原料，当时正有$j$个原料的最大耐久度

可以知道当前状态由先前的状态转移而来

【状态转移方程】$\ \ \ \ f[i][j]=max\{f[i-1][k]+a[i]*j\},-1\le k\le min(m,j+s-1)$

$updata:\qquad \qquad f[i][j]=max\{ f[i][k]\}+j\times a[i],-1\le k\le min(m,j+s-1)$

单调队列维护$f[i][k]$即可

资源分配类动态规划

• 最大乘积类型
• 背包类型

最大乘积类型

例题

【乘积最大】

设$f[i][j]$表示将$i$个乘号插入前$j$个字符中的最大乘积

【状态转移方程】$f[i][j]=max\{f[i-1][k]*sum[k+1,j]\}$

$\qquad \qquad \qquad \ \ \ \ (1\le i\le m,i+1\le j\le n,i\le k\le j-1)$

【机器分配】

设$f[i][j]$表示$i$个公司分配$j$台设备的最大盈利

【状态转移方程】$f[i][j]=max\{f[i-1][j-k]+val[i][k]\}$

【时间复杂度】$O(N\times M^2)$

我们需要记录我们需要的$f[n][m]$状态从哪里转移而来

设$root[i][j]$表示当前$f[i][j]$状态所取的$k$值，就是当前最优解时，第$i$个公司分配了多少台机器

最后递归输出即可

背包

• 01背包
• 完全背包
• 多重背包问题
• 混合背包
• 二维背包问题
• 分组背包
• 有依赖的背包

01背包

将$n$件物品填入一个容量为$v$的背包，每个物品有一个体积（费用）$c_i$，与价值$w_i$

求背包存放物品的最大价值

设$f[i][j]$表示将$i$件物品放入容量为$j$的背包的最大权值

【状态转移方程】$f[i][j]=max\{f[i-1][j],f[i-1][j-c_i]+wi[i]\}$

【时间复杂度】$O(n\times v)$

状态转移方程中$f[i-1][j]$表示当前物品不装，$f[i-1][j-w_i]+c[i]$表示装入当前物品

我们可以用滚动数组优化空间复杂度

【状态转移方程】$f[j]=max\{f[j],f[j-c_i]+wi[i]\}$

ps:

当需要背包装满时的最优解，将$f[0]=0$,$f[i-n]=-inf$

当不需要时，f[0-n]=0

我们只需要定义对于不装满的状态无意义，即负无穷，即可保证其状态不被答案所容许，即不会选到它

for(int i=1;i<=n;++i){
  for(int j=c;j>=vi[i];--j){
    f[j]=max(f[j],f[j-vi[i]]+wi[i]);
  }
}

完全背包

将$n$种物品填入一个容量为$v$的背包，每种物品有无限种可以使用。每种物品有体积（费用）$c_i$,价值$w_i$

求背包存放的最大价值

【状态转移方程】$f[i][j]=max\{f[i-1][v-k\times c_i]+k\times w_i\}$

显然三层枚举不能接受

方法一：

我们考虑转化为01背包问题，当前第$i$种物品最多可以装$v/c[i]$个

用二进制拆分，可以将其第三层优化成$log$级别的复杂度

将可以放进背包中的每个物品的个数拆分成如下几个物品：

$(1\times c_i,1\times w_i),(2\times c_i,2\times w_i),(4\times c_i,4\times w_i)$

$......(2^{k-1}\times c_i,2^{k-1}\times w_i),((a[i]-2^{k-1}+1)\times c_i,(a[i]-2^{k-1}+1)\times w_i)$

易知，此分配方式最后最多不会选取超过$a[i]$件，也保证了能够凑出所有的可能

即在答案中所有的背包个数都有可能取到

方法二：

扩大我们的状态转移方程

设$f[i][j]$表示到当前第$i$个物品，占用了$j$的重量的最大价值

此时的转移方程在$i$状态时不再是只能加入一个，而是能够在当前第$i$件物品中的状态进行转移

此时能被转移的状态已经包含了若干第$i$件物品

【状态转移方程】$f[i][j]=max\{f[i-1][j],f[i][j-c[i]]+w[i]\}$

for(int i=1;i<=n;i++){
	for(int j=c[i];j<=v;j++){
		f[j]=max(f[j-c[i]]+w[i],f[j]);
	}
}

多重背包问题

将$n$种物品填入容量为$v$的背包，每个物品可以最多取$a[i]$个，每个物品有一个体积$c[i]$,价值$w[i]$

设$f[i][j]$表示将$i$件物品放入容量为$j$的背包的最大价值

【状态转移方程】$f[i][j]=f[i-1][j-k\times c[i]]+k\times w[i],(0\le k\times w[i]\le j)$

【时间复杂度】$O(nm\sum a[i])$

采用完全背包中的一种方法，二进制转换降低第三层循环的复杂度

【时间复杂度】$O(nm\sum log a[i])$

$O(v\times n)$做法?......

int vi[101];
int wi[101];
int mi[101];
int f[N];
void pack_zo(int v,int w,int t){
  for(int i=t;i>=v;--i){
    f[i]=max(f[i],f[i-v]+w);
  }
  return ;
}
void pack_com(int v,int w,int t){
  for(int i=v;i<=t;++i){
    f[i]=max(f[i],f[i-v]+w);
  }
  return ;
}
for(int i=1;i<=n;++i){
  if(mi[i]*vi[i]>=w){
    pack_com(vi[i],wi[i],w);
    continue;
  }
  int k=1;
  while(k<=mi[i]){
    pack_zo(k*vi[i],k*wi[i],w);
    mi[i]-=k;
    k<<=1;
  }
  if(mi[i]) pack_zo(mi[i]*vi[i],mi[i]*wi[i],w);
}

混合背包

题目有时可能有多种的限制条件，即可能存在多种背包同时存在

有的物品只能取一次（01背包）

有的物品可以取无限次（完全背包）

有的物品取的次数存在上限（多重背包）

解：我们只需要在当前第$i$个背包时，判断并换一种处理方式即可

二维背包问题

对于每一件物品，有一个价值与两个属性，两个属性都有限制条件

有一个体积为$v$的背包，重量为$g$的承受能力，现在有$n$个物品，每一个物品都有重量$v[i]$，体积$c[i]$，以及费用$w[i]$

求最大的价值

设$f[i][j][k]$表示当前第$i$个物品，用了$j$的重量，$k$的体积的最大价值

【状态转移方程】$f[i][j][k]=max\{f[i-1][j][k],f[i-1][j-v[i]][k-c[i]]+w[i]\}$

如01背包，滚动数组优化到二维

【状态转移方程】$f[j][k]=max\{f[j][k],f[j-v[i]][k-c[i]]+w[i]\}$

分组背包

有$n$组物品，和一个容量为$v$的背包，第$i$组物品的第$j$件物品的体积时是$c[i][j]$，价值是$w[i][j]$

同组物品之间相互冲突，最多选一件，求最大的价值

考虑状态为每一组，当前状态为是否选择并且只选择当前组中的某一件

【状态转移方程】$f[i][j]=max\{f[i-1][j],f[i-1][j-c[i][k]]+w[i][k]\}$

同样的，我们可以用滚动数组来优化掉第一维

【状态转移方程】$f[j]=max\{f[j],f[j-c[i][k]]+w[i][k]\}$

ps:先枚举体积，在枚举组内有多少数

  for(int i=1;i<=ant;++i){
    for(int j=m;j>=0;--j){
      for(int z=1;z<=con[i];++z){
        int k=num[i][z];
        if(j-a[k].vi>=0)
        f[j]=max(f[j],f[j-a[k].vi]+a[k].wi);
      }
    }
  }

有依赖的背包

当选择某个物品时，需要附带其它的物品时，求最大价值

当只有1个或者2个附件时：

我们考虑逐一考虑一个物品是否加入，以及加入后加入哪些附件

简化条件：没有某个物品依赖于别的物品又被别的物品依赖

例题

P4158 [SCOI2009]粉刷匠

设$f[i][j][k][t]$表示粉刷到第$i$条木板的第$j$个格子时已经粉刷了$k$次，此时将其粉刷为$t$的最大正确粉刷格子数

$map[i][j]$表示当前第$i$条木板，第$j$个格子的原来的颜色

【状态转移方程】

$f[i][j][k][map_{i,j}]=max\begin{cases}f[i][j-1][k][map_{i,j}]+1\\f[i][j-1][k-1][1\&map_{i,j}]+1\end{cases}$

$f[i][j][k][1\&map_{i,j}]=max\begin{cases}f[i][j-1][k-1][map_{i,j}]\\f[i][j-1][k][1\&map_{i,j}]\end{cases}$

当$j==1$时需要特判

即需要从上一根木棍转移当当前木棍

$f[i][j][k][map_{i,j}]=max\begin{cases}f[i-1][m][k-1][1]+1\\f[i-1][m][k-1][0]+0\end{cases}$

$f[i][j][k][1\&map_{i,j}]=max\begin{cases}f[i-1][m][k-1][1]\\f[i-1][m][k-1][0]\end{cases}$

树形动态规划

例题

P1352 没有上司的舞会

设$f[i][0/1]$表示当前以$i$为根的子树，第$i$节点是否加入宴会,的最大快乐指数

$1$表示参加，$0$表示不参加

【状态转移方程】

$\begin{cases}f[i][1]=\sum f[v][0]\\f[i][0]=\sum max(f[v][1],f[v][0])\end{cases}$

$ans=max(f[g][0],f[g][1])$,$g$位任意一个入度位零的点

P2015 二叉苹果树

设$f[i][j]$表示以节点$i$为根节点的子树保留了$j$条树枝能留住的最多苹果数

【状态转移方程】

$f[i][j]=max( f[i][j-k-1]+f[v][k]+w_{u,v}),k\in(0,j-1)$

//q 为最后要求保留的枝条数
for(int i=q;i>=1;--i){
    for(int j=i-1;j>=0;--j){
        f[x][i]=max(f[x][i],f[x][i-j-1]+f[e[k].to][j]+e[k].val);
    }
}

为什么需要倒着枚举

对于当前判断的子树，只能从先前的子树的状态进行更新

当第一维从$1$开始更新时，可能会使用到当前子树更新的状态，不合法

和$01$背包类似

P1613 跑路

设$g[i][j][k]$表示$i$和$j$之间是否存在一条$2^k$的路径

设$dis[i][j]$表示$i$和$j$两点之间有了跑路器之后的最短路径

非常显然两点之间的最短路的定义发生了一些变化，考虑如何处理出新的路径关系

预处理相互两点之间的$g[i][j][k]$，以及$dis[i][j]=1$的点

for(int k=1;k<=64;++k)
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            for(int z=1;z<=n;++z)
                if(g[i][z][k-1]&&g[z][j][k-1]){
                    g[i][j][k]=1;
                    dis[i][j]=1;
                }

之后Floyd跑最短路径

for(int i=1;i<=n;++i)
    for(int j=1;j<=n;++j)
        for(int k=i;k<=n;++k)
            dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);

P1122 最大子树和

设$f[i]$表示在搜索树下，包含$i$节点的，以$i$节点为根的美丽指数之和最大的点集

【状态转移方程】$f[i]=\sum f[v]\qquad (f[v]\le 0)$

P2014 [CTSC1997]选课

设$f[i][j]$表示以$i$节点为根节点的子树中，包括$i$节点的选了$j$个节点的最大学分

此题和二叉苹果树十分类似

【状态转移方程】$f[i][j]=max(f[i][j-k]+f[v][k]),k\in (0,j-1)$

for(int i=m+1;i>=2;--i){
    for(int j=i-1;j>=0;--j){
        f[x][i]=max(f[x][i],f[x][i-j]+f[e[k].to][j]);
    }
}

小技巧：

将所有的没有入度的点连到$0$节点上，从$0$号节点开始$dp$，最后输出是$m+1$个节点的最大值

P2656 采蘑菇

$tarjan$缩点，在同一个强连通分量中的点只要进入就一定可以全部采摘

之后$spfa$判最长路

$ps:$

缩点之后的$DAG$将全部的$dis$值赋值为负无穷，将入度为零的点全部入队，只更新$s$点的$dis$值

若将所有强连通分量点的权值先赋给新图，在更新过程中会出现更新失误

只更新$s$的$dis$值保证不会将没有走到过的强连通分量用来更新

P2585 [ZJOI2006]三色二叉树

考虑在字符串的基础上$dfs$建图

int ant=1;
void build(int fa){
    int x=ant;
    if(fa!=0) add(fa,x);
    if(ai[x]==0){ return ; }
    if(ai[x]==1){
        ant++;
        build(x);
        return ;
    }
    if(ai[x]==2){
        ant++;
        build(x);
        ant++;
        build(x);
        return ;
    }
}

设$f[i][0/1/2]$表示$i$节点上分别涂$0,1,2$种颜色时，涂$1$颜色的最大数量

【状态转移方程】

当只有一个子节点：

$\begin{cases}f[u][0]+=max(f[v][1],f[v][2])\\f[u][1]+=max(f[v][0],f[v][2])\\f[u][2]+=max(f[v][0],f[v][1]) \end{cases}$

当有两个子节点：

$\begin{cases}f[u][0]+=max(f[v1][1]+f[v2][2],f[v1][2]+f[v2][1])\\f[u][1]+=max(f[v1][0]+f[v2][2],f[v1][2]+f[v2][0])\\f[u][2]+=max(f[v1][0]+f[v2][1],f[v1][1]+f[v2][0])\end{cases}$

同理最小值，改成$min$即可

P1273 有线电视网

设$f[i][j]$表示以$i$节点为根的子树中有$j$个叶子节点的最大盈利

【状态转移方程】$f[u][j]=max(f[u][j-k]+f[v][k]-w_{u,v}),j\in (0,m]$

但是发现会$T$掉，原因是$j$枚举了太多没有必要的状态

我们将$j$的范围缩小，$j\in (0,sum]$,$sum$表示当前已知的叶子节点数

int f[N][N];
int dfs(int x){
    if(x>n-m){
        f[x][1]=ai[x];
        return 1;
    }
    int sum=0;
    for(int k=head[x];k;k=e[k].next){
        int v=e[k].to;
        int t=dfs(v);
        sum+=t;
        for(int i=sum;i>=1;--i){
            for(int j=i;j>=0;--j){
                f[x][i]=max(f[x][i],f[x][i-j]+f[v][j]-e[k].val);
            }
        }
    }
    return sum;
}

P2016 战略游戏

设$f[i][1/0]$表示以$i$为根的子树中，当前$i$节点安排或者不安排士兵的最小安排士兵数

【状态转移方程】$\begin{cases}f[u][0]=\sum f[v][1]\\f[u][1]=min(f[v][1],f[v][0])+1\end{cases}$

区间与环形动态规划

例题

P1880 [NOI1995]石子合并

设$f[i][j][1/0]$表示区间$[i,j]$合并成一堆石子的最大，最小得分

$sum[i][j]$表示区间$[i,j]$的和

【状态转移方程】$\begin{cases}f[i][j][1]=max(f[i][k][1],f[k+1][j][1])+sum[i][j]\\f[i][j][0]=min(f[i][k][0],f[k+1][j][0])+sum[i][j]\end{cases}$

将原来的石子序列复制一边变成长度为$2n$的序列

在$[i,i+n-1]$中枚举答案的最大值

P1063 能量项链

和石子合并十分类似

设$f[i][j]$表示区间$[i,j]$合并成一个珠子的最大能量

$ai[ ]$表示输入的头指针序列

【状态转移方程】$f[i][j]=max(f[i]k],f[k+1][j])+ai[i]*ai[k+1]*ai[r+1]$

成环的处理方法如石子合并

P4170 [CQOI2007]涂色

设$f[i][j]$表示将区间$[i,j]$染成正确颜色的最下涂色次数

【状态转移方程】$f[i][j]=\begin{cases}min(f[i][j-1],f[i+1][j])\qquad (s[i]==s[j])\\min(f[i][k]+f[k+1][j])\ \ \ \qquad (s[i]!=s[j])\end{cases}$

初始化$f[ ][ ]=inf$，$f[i][i]=1$

为什么只需要判断$s[i]==s[j]$就可以得到正解？

我们只需要考虑答案的方案是否有可能在结果中体现即可

对于所有能够简化涂色的方案都通过这个判断得以加入更新，即可以得到正解

P3146 [USACO16OPEN]248 G

设$f[i][j]$表示区间$[i,j]$可以合并成的最大的数

当前区间可能无法合并成一个数，只需要将其赋值为$0$即可

【状态转移方程】$f[i][j]=max(f[i][k]+1)\qquad (f[i][k]==f[k+1][j]])$

初始化$f[ ]=0$,$f[i][i]=ai[i]$

P2858 [USACO06FEB]Treats for the Cows G/S

设$f[i][j]$表示将区间$[i,j]$的零食售出的最大收益

【状态转移方程】$f[i][j]=max(ant\times ai[l]+f[l+1][r],f[l][r-1]+ant\times ai[r])$

$dfs$写法

int f[N][N];
void dfs(int l,int r,int ant){
    if(f[l][r]) return ;
    if(l==r){
        f[l][l]=ant*ai[l];
        return ;
    }
    dfs(l+1,r,ant+1); dfs(l,r-1,ant+1);
    f[l][r]=max(ant*ai[l]+f[l+1][r],f[l][r-1]+ai[r]*ant);
}

为什么已经更新过的$f[i][j]$可以直接引用

当将要更新$f[i][j]$时，一定已经有$sum\_all-sum\_qu[i,j]$个零食被售空

即往后的所有的状态都已经处理过

P3205 [HNOI2010]合唱队

设$f[i][j][0/1]$表示区间$[i,j]$构成最终合法状态，最后一个元素插入到左边$'0'$,右边$'1'$的合法方案数

【状态转移方程】

$\begin{cases}f[i][j][0]+=\begin{cases}f[i+1][j][0]\qquad (a[i]<a[i+1])\\f[i+1][j][1]\qquad(a[i]<a[j])\end{cases}\\f[i][j][1]+=\begin{cases}f[i][j-1][0]\qquad (a[j]>a[i])\\f[i][j-1][1]\qquad(a[j]>a[j-1])\end{cases}\end{cases}$

递归记忆化搜索：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#define ll long long
#define N 2010
const int inf=2147483600;
const ll mod=19650827;
using namespace std;
int n;
ll ai[N];
ll f[N][N][2];
ll dfs(int l,int r,int k){
    if(f[l][r][k]!=-1) return f[l][r][k];
    int ans=0;
    if(!k){
        if(ai[l]<ai[l+1])
            ans+=dfs(l+1,r,0);
        if(ai[l]<ai[r])
            ans+=dfs(l+1,r,1);
    }else{
        if(ai[r]>ai[l])
            ans+=dfs(l,r-1,0);
        if(ai[r]>ai[r-1])
            ans+=dfs(l,r-1,1);
    }
    return f[l][r][k]=ans%mod;
}
int main()
{
    scanf("%d",&n);
    memset(f,-1,sizeof(f));
    for(int i=1;i<=n;++i){
        scanf("%lld",&ai[i]);
    }
    for(int i=1;i<=n;++i){
        f[i][i][0]=1;
        f[i][i][1]=0;
    }
    cout<<(dfs(1,n,0)+dfs(1,n,1))%mod<<endl;
    return 0;
}

动态规划：

#include<iostream>
#include<cstdio>
#include<cmath>
#define ll long long
#define N 2010
const int mod=19650827;
using namespace std;
int n;
int a[N];
int f[N][N][2];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;++i){
        f[i][i][0]=1; f[i][i][1]=0;
    }
    for(int z=1;z<n;++z){
        for(int i=1,j=i+z;i<n&&j<=n;++i,j=i+z){
            if(a[i]<a[i+1]){
                f[i][j][0]=(f[i][j][0]+f[i+1][j][0])%mod;
            }
            if(a[i]<a[j]){
                f[i][j][0]=(f[i][j][0]+f[i+1][j][1])%mod;
            }
            if(a[j]>a[i]){
                f[i][j][1]=(f[i][j][1]+f[i][j-1][0])%mod;
            }
            if(a[j]>a[j-1]){
                f[i][j][1]=(f[i][j][1]+f[i][j-1][1])%mod;
            }
        }
    }
    cout<<(f[1][n][0]+f[1][n][1])%mod<<endl;
    return 0;
}

P1005 矩阵取数游戏

此题和$P2858$简直一模一样....

就是求$n$遍，之后高精相加

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define ll __int128
#define N 101
using namespace std;
inline int read() 
{
    int X=0,w=1;
    char ch=getchar();
    while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();
    return X*w;
}
void print(ll x)
{
    if(!x) return;
    if(x) print(x/10);
    putchar(x%10+'0');
}
ll n,m;
ll ai[N][N];
ll f[N][N][N];
ll ci[N];
void dfs(int k,int l,int r,int t){
    if(f[k][l][r]!=-1) return ;
    if(l==r){
        f[k][l][l]=ai[k][l]*ci[t];
        return ;
    }
    dfs(k,l,r-1,t+1); dfs(k,l+1,r,t+1);
    f[k][l][r]=max(f[k][l][r-1]+ai[k][r]*ci[t],ai[k][l]*ci[t]+f[k][l+1][r]);
    return ;
}
ll ans=0;
int main()
{
    n=read();
    m=read();
    memset(f,-1,sizeof(f));
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            ai[i][j]=read();
        }
    }
    ci[0]=1;
    for(int i=1;i<=m;++i){
        ci[i]=ci[i-1]*2;
    }
    for(int z=1;z<=n;++z){
        dfs(z,1,m,1);
        ans+=f[z][1][m];
    }
    if(!ans) cout<<0<<endl;
    else
    print(ans);
    return 0;
}

P1220 关路灯

设$f[i][j]$表示将区间$[i,j]$的灯全部熄灭的最小耗电量

我们考虑在区间中，最后只可能站在首位或者末尾，即当前状态$f[i][j]$由$f[i][j-1]$或者$f[i+1][j]$转移而来

我们当前$f[i][j]$表示的是全局耗电量

我们设$sum[i]$表示区间$[1,i]$在单位时间为$1$时的耗电量

我们从状态$f[i][j-1]$或者$f[i+1][j]$转移时，需要计入的耗电量是当前除了已经熄灭的灯之外的灯的单位时间总耗电量乘上时间

【状态转移方程】

$ f[i][j][0]=min\begin{cases}f[i+1][j][1]+S(i,j)\times(sum[i]+sum[n]-sum[j])\f[i+1][j][0]+S(i,i+1)\times(sum[i]+sum[n]-sum[j]))\end{cases}$

$ f[i][j][1]=min\begin{cases}f[i][j-1][0]+S(i,j)\times(sum[i-1]+sum[n]-sum[j-1])\f[i][j-1][1]+S(j-1,j)\times(sum[i-1]+sum[n]-sum[j-1]))\end{cases}$

$S(i,j)$表示节点$i$到节点$j$的距离

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
#define N 101
using namespace std;
ll n,m;
struct ndoe{
    ll x;
    ll val;
}a[N];
ll sum[N];
ll coun(int x,int y){
    return a[y].x-a[x].x;
}
ll f[N][N][2];
int main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%lld%lld",&a[i].x,&a[i].val);
        sum[i]=sum[i-1]+a[i].val;
    }
    memset(f,0x3f,sizeof(f));
    f[m][m][0]=0; f[m][m][1]=0;
    for(int z=1;z<n;++z){
        for(int i=1,j=i+z;i<n&&j<=n;++i,j=i+z){
            f[i][j][0]=min(f[i+1][j][1]+coun(i,j)*(sum[i]+sum[n]-sum[j]),f[i+1][j][0]+coun(i,i+1)*(sum[i]+sum[n]-sum[j]));
            f[i][j][1]=min(f[i][j-1][0]+coun(i,j)*(sum[i-1]+sum[n]-sum[j-1]),f[i][j-1][1]+coun(j-1,j)*(sum[i-1]+sum[n]-sum[j-1]));
        }
    }
    cout<<min(f[1][n][0],f[1][n][1])<<endl;
    return 0;
}

CF607B Zuma

设$f[i][j]$表示区间$[i,j]$全部移除的最小移除次数

【状态转移方程】$f[i][j]=min\begin{cases}f[i+1][j-1]\qquad (a[i]==a[j])\\min(f[i][k]+f[k][j])\end{cases}$

$ps:$

初始化全部的$f[i][i]=1$,和长度为$2$的$f[ ]$ ,只枚举长度为3以上的状态，防止越界

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
#define N 510
using namespace std;
int n;
int ai[N];
int f[N][N];
int main()
{
    memset(f,0x3f,sizeof(f));
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d",&ai[i]);
    }
    for(int i=1;i<=n;++i){ f[i][i]=1; }
    for(int i=1;i<n;++i){
        if(ai[i]==ai[i+1]){
            f[i][i+1]=1;
        }else{
            f[i][i+1]=2;
        }
    }
    for(int z=2;z<n;++z){
        for(int i=1,j=i+z;i<=n-2&&j<=n;++i,j=i+z){
            if(ai[i]==ai[j]){
                f[i][j]=f[i+1][j-1];
            }
            for(int k=i;k<j;++k){
                f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
            }
        }
    }
    cout<<f[1][n]<<endl;
    return 0;
}

状态压缩动态规划

例题

P1896 [SCOI2005]互不侵犯

设$f[i][j][k]$表示在前$i$行(包括第$i$行)，当前状态为$j$一共安排了$k$个士兵的方案数

每一行的状态压缩，$1$表示有士兵$0$表示没有

预处理出每一行中有可能合法的状态，以及合法状态$ai[i]$中有多少个$1$,$con[i]$

for(int i=0;i<(1<<n);++i){
    if((((i<<1)|(i>>1))&i)==0) ai[++ant]=i;
    else continue;
    int s=0;
    int k=i;
    while(k){
        if(k&1) s++;
        k>>=1;
    }
    con[ant]=s;
}

【状态转移方程】$f[i][j][k]+=f[i-1][j'][k-con[j]]$

$j$与$j'$是枚举的两个合法的转移状态

P1879 [USACO06NOV]Corn Fields G

设$f[i][s]$表示当前第$i$行状态为$s$的方案数

初始化一行中所有的合法方案数，以及将一行中不能种草的格子存为一种状态

【状态转移方程】$f[i][s]+=f[i-1][s']$

$s$与$s'$是两种合法的转移状态

#include<iostream>
#include<cmath>
#include<cstdio>
#define ll long long
#define N 40110
const int mod=100000000;
using namespace std;
int n,m;
int map[20][N];
int no[N];
int ai[N];
int ant;
ll f[20][N];
int main()
{
    scanf("%d%d",&m,&n);
    for(int i=1;i<=m;++i){
        for(int j=1;j<=n;++j){
            scanf("%d",&map[i][j]);
            map[i][j]=1^map[i][j];
        }
    }
    for(int i=1;i<=m;++i){
        int s=0;
        for(int j=1;j<=n;++j){
            s+=(map[i][j]<<(j-1));
        }
        no[i]=s;
    }
    for(int i=0;i<(1<<n);++i){
        if((((i<<1)|(i>>1))&i)==0){
            ai[++ant]=i;
        }
    }
    for(int i=1;i<=ant;++i){
        if((ai[i]&no[1])==0){
            f[1][i]=1;
        }
    }
    for(int i=2;i<=m;++i){
        for(int j=1;j<=ant;++j){
            int v=ai[j];
            if(v&no[i]) continue;
            for(int k=1;k<=ant;++k){
                int u=ai[k];
                if((u&no[i-1])||((u&v)!=0)) continue;
                f[i][j]=(f[i][j]+f[i-1][k])%mod;
            }
        }
    }
    ll ans=0;
    for(int i=1;i<=ant;++i){
        ans=(ans+f[m][i])%mod;
    }
    cout<<ans<<endl;
    return 0;
}

P2051 [AHOI2009]中国象棋

此题的状态转移方程，十分鬼畜

设$f[i][j][k]$表示在前$i$行中有$j$列有两个棋子，有$k$列有两个棋子

【状态转移方程】

当不放入棋子时：

$f[i][j][k]=f[i-1][j][k]$

当只放入一个棋子时：

$1.$当放入到放有一个棋子的列中时

$f[i][j][k]+=f[i-1][j+1][k-1]\times (j+1)$

$2.$当放入到没有棋子的列中时

$f[i][j][k]+=f[i-1][j-1][k]\times(m-(j-1)-k)$

当放入两个棋子时：

$1.$一个放入有一个棋子的列中，一个放入，没有棋子的列中

$f[i][j][k]+=f[i-1][j][k-1]\times j\times (m-j-(k-1))$

$2.$将棋子都放入没有棋子的列中时

$f[i][j][k]+=f[i-1][j-2][k]\times C_{m-(j-2)-k} ^2$

$3.$将棋子都放入只有一个棋子的列中

$f[i][j][k]+=f[i-1][j+2][k-2]\times C_{j+2}^2$

f[0][0][0]=1;
for(int i=1;i<=n;++i){
    for(int j=0;j<=m;++j){
        for(int k=0;k<=(m-j);++k){
            f[i][j][k]=f[i-1][j][k];
            if(k>=1)f[i][j][k]+=f[i-1][j+1][k-1]*(j+1);
            if(j>=1)f[i][j][k]+=f[i-1][j-1][k]*(m-(j-1)-k);
            if(k>=2)f[i][j][k]+=f[i-1][j+2][k-2]*(((j+2)*(j+1))/2);
            if(k>=1)f[i][j][k]+=f[i-1][j][k-1]*j*(m-j-(k-1));
            if(j>=2)f[i][j][k]+=f[i-1][j-2][k]*C(m-(j-2)-k);
            f[i][j][k]%=mod;
        }
    }
}

P2704 [NOI2001]炮兵阵地

考虑到当前的状态必须从前面的两层状态中转移过来，所以必须要记录两层状态

设$f[i][j][k]$表示当前第$i$行的状态为$j$前一行的状态为$k$的最大安放炮兵数量

预处理每一行的所有合法状态

void dfs(int h,int x){
    if(x==m){
        ant[h]++;
        int s=0;
        for(int i=1;i<=m;++i){
            if(xu[i]==1)
                con[h][ant[h]]++;
            s+=(xu[i]<<(i-1));
        }
        ai[h][ant[h]]=s;
        return ;
    }
    if(!mp[h][x+1]&&!vis[x+1]){
        vis[x+1]=1; vis[x+2]=1; vis[x+3]=1;
        xu[x+1]=1;
        dfs(h,x+1);
        vis[x+1]=0; vis[x+2]=0; vis[x+3]=0;
    }
    xu[x+1]=0;
    dfs(h,x+1);
    return ;
}


for(int i=1;i<=n;++i){
    memset(vis,0,sizeof(vis));
    dfs(i,0);
}

$con[i][j]$表示第$i$行第$j$列的状态中有多少个$1$，即有多少个炮兵

$ai[i][j]$表示第$i$行第$j$列的状态

$ant[i]$表示第$i$行中有多少合法的状态

【状态转移方程】$f[i][j][k]=max(f[i-1][k][z]+con[i][j])$,$j,k,z$为三个合法的转移状态

预处理：

ant[0]=1;
int ans=-inf;
for(int i=1;i<=ant[1];++i){
    for(int j=1;j<=N;++j){
        f[1][i][j]=con[1][i];
        ans=max(ans,f[1][i][j]);
    }
}

$dp:$

for(int i=2;i<=n;++i){
    for(int j=1;j<=ant[i];++j){
        for(int k=1;k<=ant[i-1];++k){
            for(int z=1;z<=ant[i-2];++z){
                if(((ai[i][j]&ai[i-1][k])==0)&&((ai[i][j]&ai[i-2][z])==0))
                    f[i][j][k]=max(f[i][j][k],f[i-1][k][z]+con[i][j]);
            }
        }
    }
}

​

P3694 邦邦的大合唱站队

$ai[i]$表示输入的队伍编号序列

设$f[i]$在队伍排列为$i$状态的最小出队次数，如$1101$表示乐队$1,2,4$从头开始依次排列完成

设$sum[i]$表示编号为$i$的乐队一共有多少人

设$s[i][j]$表示在前$i$个位置中有编号为$j$的乐队多少人

设$coun[i]$表示状态为$i$的队伍已经拍好了多少人

【状态转移方程】

预处理：

$s[i][j]=\begin{cases}s[i-1][j]+1\qquad (ai[i]==j)\\s[i-1][j]\end{cases}$

$f[0]=0$

for(int i=1;i<=n;++i){
    for(int j=1;j<=m;++j){
        if(ai[i]==j){
            s[i][j]=s[i-1][j]+1;
        }else{
            s[i][j]=s[i-1][j];
        }
    }
}
memset(f,0x3f,sizeof(f));
f[0]=0;

$dp:$

$coun[s|j]=coun[s]+sum[j]$

$l=coun[s],r=l+sum[j]$

$f[s|j]=min(f[s]+sum[j]-s[r][j]+s[l][j])$

for(int i=0;i<(1<<m);++i){
    for(int j=1;j<=m;++j){
        int v=1<<(j-1);
        if(v&i) continue;
        int l=coun[i];
        int r=l+sum[j];
        f[i|v]=min(f[i|v],f[i]+sum[j]-s[r][j]+s[l][j]);
        coun[i|v]=coun[i]+sum[j];
    }
}

P1441 砝码称重

$dfs$搜索出只选取$n-m$个砝码的状态

void dfs(int x,int d){
    if(d>(n-m)) return ;
    if(x==n){
        if(d==(n-m)) dp();
        return ;
    }
    vis[x+1]=1;
    dfs(x+1,d+1);
    vis[x+1]=0;
    dfs(x+1,d);
}

对于每一个状态进行$dp$

设$f[i][j]$表示前$i$个砝码为能否称量出重量$j$的物品

【状态转移方程】$f[i][j]=1 （f[i-1][j]==1或f[i-1][j-ai[i]]==1）$

$ans=\sum_{j=1}^{tot} f[n][j]$

void dp(){
    memset(f,0,sizeof(f));
    f[0][0]=1;
    for(int i=1;i<=n;++i){
        if(!vis[i]){
            for(int j=0;j<=sum[i];++j){
                f[i][j]=f[i-1][j];
            }
        }else{
            for(int j=0;j<=sum[i];++j){
                if(f[i-1][j]){
                    f[i][j]=1;
                }
                if(j>=ai[i]&&f[i-1][j-ai[i]]){
                    f[i][j]=1;
                }
            }
        }
    }
    int s=0;
    for(int i=1;i<=sum[n];++i){
        if(f[n][i]) s++;
    }
    ans=max(ans,s);
    return ;
}

类似与$01$背包，滚动数组滚动一维

【状态转移方程】$f[j]=1\qquad (f[j]==1或f[j-ai[i]]==1)$

void dp(){
    int s=0;
    memset(f,0,sizeof(f));
    f[0]=1;
    for(int i=1;i<=n;++i){
        if(!vis[i])
            continue;
        for(int j=sum[i];j>=ai[i];--j){
            if(f[j-ai[i]]&&!f[j]){
                f[j]=1;
                s++;
            }
        }
       
    }
    ans=max(ans,s);
    return ;
}