动态规划
目录若起始时规定开始状态的\(j\)，可使\(i\)从\(n\)到0，输出\(dp[0][j]\)。
可链接区间：可开\(dp[maxn][2]\)表示是否连接，也可一维\((dp[i-1]+a[i],\ dp[i-2]+b[i])\)。
\(dp[i]\)定义：要求\(i\)为严格连续则定义\(dp[i]\)为\(0-i\)且以\(i\)结尾的最优解，若要求\(i\)可为离散则定义\(dp[i]\)为\(0-i\)最优解。
背包
最好从1开始计算物品，因为0可当作什么也没选。
0-1背包
已知条件有第\(i\)个物品的重量\(w_i\)，价值\(v_i\)，以及背包的总容量\(m\)。
\(f_{i,j}\) 为在只能放前\(i\)个物品的情况下，容量为\(j\)的背包所能达到的最大总价值。
\(f_{i,j}=\max(f_{i-1,j},f_{i-1,j-w_i}+v_i)\)
\(fj=\max(f_j,f_{j-w_i}+v_i)\) 从右到左。
完全背包
与 0-1 背包的区别仅在于一个物品可以选取无限次，而非仅能选取一次。
\(f_{i,j}=\max_{k=0}^{+\infty}(f_{i-1,j-k\times w_i}+k\times v_i)\)
\(f_{i,j}=\max(f_{i-1,j},f_{i,j-w_i}+v_i)\)
\(fj=\max(f_j,f_{j-w_i}+v_i)\) 从左到右
类似背包
poj-1015:从\(n\)个物品(有属性\(x，y\))中选出\(m\)个，要求在\(\min(\mid\sum x-\sum y\mid)\)的前提下
\(\max(\sum x +\sum y)\)，三重循环，\(j\)当前正在选择，\(k\)当前差，\(i\)当前可在选，\(dp[j][k]\)当前最大和。
注：输出时不再按照从小到大选择\(i\)，不能仅使用函数递归，应重排序。
参考题解。
错误代码：
path处理错误，eg：(1)和(2)同时是\(\max(dp[i][j])\)只能储存一个path，由比较句中\(>=\)或\(>\)决定选择后来的或先来的。选择后将少计算情况。
for(int j=0; j<m; j++){
for(int k=0; k<=m*40; k++){
if(dp[j][k]>=0){
for(int i=1; i<=n; i++){
if(dp[j][k]+x[i]+y[i]>dp[j+1][k+x[i]-y[i]]){
a=j, b=k;
while(path[a][b]!=i && a>0){
b-=x[path[a][b]]-y[path[a][b]];
a--;
}
if(a==0){//未选
dp[j+1][k+x[i]-y[i]]=dp[j][k]+x[i]+y[i];
path[j+1][k+x[i]-y[i]]=i;
}
}
}
}
}
}
状压DP
例：工作排序，状态从\(n!\)到\(1<<n-1\)，外层循环\(1<<n-1\)，内层循环\(n\)。
没有要求整项工作在规定时间做完，所以不能贪心。
#define maxn 20
#define maxm 1<<20
#define inf 1e9
struct node{
char s[105];
int d, c;
}a[maxn];
int dp[maxm], t[maxm];
int pre[maxm];
void op(int x){ //注意输出
if(x==0) return;
op(x^(1<<pre[x]));
printf("%s\n", a[pre[x]].s);
}
int main(){
int T, n, m;
cin>>T;
while(T--){
scanf("%d", &n);
for(int i=0; i<n; i++)
scanf("%s %d %d", a[i].s, &a[i].d, &a[i].c);
//name, deadline, continue_time
m=1<<n;
dp[0]=0, t[0]=0;
for(int i=1; i<m; i++){
dp[i]=(int)inf;
for(int j=0; j<n; j++){
int d=a[j].d, c=a[j].c, bit=1<<j;
if((i&bit)==0) continue;
int dt=t[i^bit]+c-d;
if(dt<0) dt=0;
if(dp[i]>=dp[i^bit]+dt){
dp[i]=dp[i^bit]+dt;
t[i]=t[i^bit]+c;
pre[i]=j;
}
}
}
printf("%d\n", dp[m-1]);
op(m-1);
}
return 0;
}
区分：每项工作有continue和固定start，则简单\(dp\)。\(O(n^2)\)
区间DP
卡特兰分法
多边形切割
将多边形可按卡特兰数分法分割，以\(i,j\)为顶点分割线有代价\(f(i,j)\)，求最小分法。
初始化\(dp[i][i+1]=cost[i][i+1]=0\)记忆化搜索即可。\(O(n^3)\)
ll co(int i, int j){
if(c[i][j]!=-1) return c[i][j];
node a=h[i], b=h[j];
return c[i][j]=Abs(a.x+b.x)*Abs(a.y+b.y)%m;
}
ll sol(int i, int j){
if(dp[i][j]!=-1) return dp[i][j];
ll res=inf;
for(int k=i+1; k<j; k++){
res=min(res, sol(i, k)+co(i, k)+sol(k, j)+co(k, j));
}
return dp[i][j]=res;
}
栈的进出
给定每个时刻栈顶元素，求最小输入数据个数。
初始化\(dp[i][i]=1\)，\(dp[i+1][i]=0\)可不写，\(dp[i][j]=dp[i][j-1]\)(选新的)，\(dp[i][j]=dp[i][k]+dp[k+1][j-1],\ \{k\mid a[k]==a[j]\ \&\&\ i<=k<j\}\)(用以前的)。\(O(n^3)\)
int sol(int i, int j){
if(dp[i][j]!=-1) return dp[i][j];
int res=sol(i, j-1)+1;
if(a[j]==a[j-1]) res=min(res, dp[i][j-1]);
for(int k=i; k<=j-2; k++){
if(a[k]==a[j])
res=min(res, sol(i, k)+sol(k+1, j-1));
}
return dp[i][j]=res;
}
括号配对
s应为: ab 或 (a)。
不连续：即())()=4。
其中一种方法：
\(dp[i][j]=dp[i+1][j-1]+2,\ \{a[i]=='(' \&\& a[j]==')'\}\)，\(dp[i][j]=dp[i][k]+dp[k+1][j],\ \{k\mid i<=k, k+1<=j\}\)
取最小值即可。
连续：即())()=2。(没有题目提交过，不保证正确)，用栈或者：
\(dp[i][j]=1,\ \{a[i]=='(' \&\& a[j]==')' \&\& dp[i+1][j-1]\}\)，\(dp[i][j]=1,\ \{dp[i][k]\&\&dp[k+1][j]\&\&i<k,\ k+1<j\}\)
数列取数
数列两端取数
\(dp[i][j]=F(f(dp[i+1][j],\ a[i]),\ f(dp[i][j-1],\ a[j]))\)
//eg:score=cnt(选取顺序)*a[i],求maxn(score),不用初始化
for(int i=n; i>=1; i--){
for(int j=i; j<=n; j++){
dp[i][j]=max(dp[i+1][j]+a[i]*(n-(j-i)),
dp[i][j-1]+a[j]*(n-(j-i)));
}
}
数列中间取数
1，n最后取，\(dp[i][j]\)为去完\(i,j\)中间的数最小或最大代价。
\(dp[i][j]=dp[i][k]+dp[k][j]+f[i,k,j]\)，最后取\(k\)。
int sol(int i, int j){
if(dp[i][j]!=-1) return dp[i][j];
if(i+1==j) return dp[i][j]=0;
int res=(int)inf;
for(int k=i+1; k<j; k++){
res=min(res, sol(i, k)+sol(k, j)+a[i]*a[k]*a[j]);
}
return dp[i][j]=res;
}
可入栈的取数
已有顺序1到n，和代价a[i]，个人代价为前面出场人数乘a[i]，有一空栈可用于调整顺序。
//错误：没有考虑中间出场
int solwr(int i, int j){
if(dp[i][j]!=-1) return dp[i][j];
if(i>=j) return dp[i][j]=0;
return dp[i][j]=min(s[j]-s[i], a[i]*(j-(i+1)+1))+solwr(i+1, j);
}
int sol(int i, int j){
if(dp[i][j]!=-1) return dp[i][j];
if(i>=j) return dp[i][j]=0;
int res=s[j]-s[i]+sol(i+1, j);
for(int k=i+1; k<=j; k++){
res=min(res, sol(i+1, k)+a[i]*(k-(i+1)+1)+
(s[j]-s[k])*(k-i+1)+sol(k+1, j));
}
return dp[i][j]=res;
}
段覆盖
覆盖空字符串
每次可将\(a\)的一连续段改为某一字符，求将空字符串\(a\)修改为\(s\)的最小修改次数。
没有重复字符：\(dp[j][i]=dp[j+1][i]+1=dp[j][k]+dp[k+1][i]\)
显然，必须采取先覆盖两端边界为最优解，故：
\(s[j]==s[i]:\ dp[j][i]=dp[j+1][i]=dp[j][i-1]\)
这里固定\(i\)即可计算。
memset(dp, 0, sizeof(dp));
for(int i=0; i<n; i++){
for(int j=i; j>=0; j--){
dp[j][i]=dp[j+1][i]+1;
for(int k=j+1; k<=i; k++){
if(s[j]==s[k])
dp[j][i]=min(dp[j+1][k]+dp[k+1][i], dp[j][i]);
}
}
}
覆盖非空字符串
先计算空字符串，\(S[i]=min(dp[0][i],\ S[i-1])+1\)。
\(a[k]==s[k]:\ S[i]=min(S[i],\ S[k-1]+dp[k+1][i])\)
S[0]=(a[0]==s[0]?0:1);
for(int i=1; i<n; i++){
S[i]=min(dp[0][i], S[i-1]+1);
for(int k=0; k<=i; k++){
if(a[k]==s[k]) S[i]=min(S[i], S[k-1]+dp[k+1][i]);
}
}
常见
最长上升子序列
\(dp[i]\)初始化为\(1\)。\(O(n^2)\)
例：叠加最高立方体。
例：HDU-1257，不是多次查找最长不严格下降子序列，而是直接找最长上升子序列。若\(ans\)大于最长上升子序列，必有一个不在序列中点当起点，该点可来源于前一个起点非严格连续下降，故矛盾；若\(ans\)小于最长上升子序列，必有一个在序列中点不当起点，该点为前缀最大值，必为起点，故矛盾。
错误代码：
ans=0;
for(int i=0; i<n; i++){
dp[i]=1;
for(int j=0; j<i; j++){
if(a[j]<a[i]){
dp[i]=max(dp[i], dp[j]+1);
ans=max(ans, dp[i]);//可能永远不会执行这一句，而ans应为1
}
}
}
正确代码：
for(int i=0; i<n; i++){
dp[i]=1;
for(int j=0; j<i; j++){
if(a[j]<a[i]){
dp[i]=max(dp[i], dp[j]+1);
}
}
ans=max(ans, dp[i]);
}
//or 初始化ans=1
\(o(n\log(n))\)
int a[maxn], b[maxn];
int dp(int n){
int len, pos;
b[1]=a[1];
len=1;//b的size
for(int i=2; i<=n; i++){
if(a[i]>=b[len]) b[++len]=a[i];//非降序列
else{ //第一个比 a[i] 大的位置
pos=upper_bound(b+1, b+1+len, a[i])-b;
b[pos]=a[i];
}
}
return len;
}
最长公共子序列
\(O(n^2)\)
//x,y前各加了一个不相等的无关字符,使字符串向后移一位
if(x[i]==y[j]) dp[i][j]=dp[i-1][j-1]+1;
else dp[i][j]=max(dp[i][j-1], dp[i-1][j]);
空间优化
c^=1;//使用亦或翻滚
for(int j=1; j<sy; j++){
if(x[i]==y[j]) dp[j][c]=dp[j-1][c^1]+1;
else dp[j][c]=max(dp[j][c^1], dp[j-1][c]);
}
最大对称矩阵
\(dp[i][j]\)为以\((i,j)\)结尾的最大正方形。
（左上右下对称）\(dp[i][j]=min(dp[i-1][j-1], \min(k)),\{k\mid a[i-k][j]!=a[i][j-k]\}\)
数列单调代价
可加减调整数列为非严格递增数列，每次调整代价\(abs(pre-now)\)。
因为调整后必为原数组中的数，离散化\(a[i]\)。\(dp[i][j]\)为选取第\(i\)个数为\(j\)的最小代价。
\(dp[i][j]=\Delta a+\min(dp[i][k]),\ \{k\mid 1<=k<=j\}\)
一维：\(dp[j]=\Delta a+pm[j]\)，\(pm[j]\)为上一行\(\min(dp[k]),\ \{k\mid 1<=k<=j\}\)
sort(b+1, b+1+n);
pm[0]=(ll)inf;
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
dp[j]=pm[j]+Abs(a[i]-b[j]);
pm[j]=min(dp[j], pm[j-1]);
}
}
斜率DP
eg:HDU-3507 ，给出数列\(a[i]\)，打印连续数列段\(k\)到\(j\)代价为\((sum[j]-sum[k-1])^2+m\)，求打印全部数列最小代价。
比较\(k+1,\ j+1\)哪个更适合和\(i\)放一起，\(k+1<j+1<i\)：
\(dp[j]+(s[i]-s[j])^2+m<=dp[k]+(s[i]-s[k])^2+m\)
\(dp[j]+s[j]^2-2\times s[i]\times s[j]<=dp[k]+s[k]^2-2\times s[i]\times s[k]\)
\((dp[j]+s[j]^2)-(dp[k]+s[k]^2)<=2\times(s[j]-s[k])\times s[i]\)
\(K=\frac{(dp[j]+s[j]^2)-(dp[k]+s[k]^2)}{2\times(s[j]-s[k])\times s[i]}<=s[i]\)
即：\(K<s[i]\)时，大的\(j+1\)更合适。
一至三点\(k<j<i\)，判断谁更适合点\(x\)。
下凸：\(K_1<K_2\)：
1）\(K_1<K_2<s[x]\)，\(i\)最优
2）\(K_1<s[x]<K_2\)，\(j\)最优
3）\(s[x]<K_1<K_2\)，\(k\)最优
故可采用维持队列下凸，仅比较相邻点可找到最优，即在\(O(n)\)内完成。
下凹：\(K_1>K_2\)：
1）\(s[x]>K_1>K_2\)，\(i\)最优
2）\(K_1>s[x]>K_2\)，\(k,\ i\)都比\(j\)优，需再比较\(K_{k,\ i}\)与\(s[x]\)判断最终谁优。
3）\(K_1>K_2>s[x]\)，\(k\)最优。
故可采用维持队列下凸，需比较任意两点可找到最优，即在\(O(n^2)\)内完成。
本题采用\(O(n^2)\)超时，故维护下凸即可。
证明如下操作后，最终中间过程以及最终获得队列必为下凸：采用数学归纳。
ll dp[maxn], a[maxn], s[maxn], m;
int q[maxn], n;
ll up(int j, int k){
return (dp[j]+s[j]*s[j])-(dp[k]+s[k]*s[k]);
}
ll dow(int j, int k){
return 2*(s[j]-s[k]);
}
ll sol(int j, int i){//选j+1到i
return dp[j]+m+(s[i]-s[j])*(s[i]-s[j]);
}
int main(){
while(scanf("%d%lld", &n, &m)!=EOF){
for(int i=1; i<=n; i++){
scanf("%lld", &a[i]);
s[i]=s[i-1]+a[i];
}
int st=0, t=0;
q[t++]=0;
for(int i=1; i<=n; i++){
while(st+1<t && up(q[st+1], q[st])<=s[i]*dow(q[st+1], q[st]))
st++;
dp[i]=sol(q[st], i);
while(st+1<t && up(i, q[t-1])*dow(q[t-1], q[t-2])<=
up(q[t-1], q[t-2])*dow(i, q[t-1])) t--;
q[t++]=i;
}
printf("%lld\n", dp[n]);
}
}