前言
此类知识点大纲中并未涉及，所以【5】是我自己的估计，后带星号表示估计，仅供参考。
坐标规则类DP
通式
d p [ i ] [ j ] = max / min { d p [ i − k 1 ] [ j − k 2 ] } + w ( i , j ) dp[i][j]=\max/\min\{dp[i-k_{1}][j-k_{2}]\}+w(i,j) dp[i][j]=max/min{dp[i−k1][j−k2]}+w(i,j)
其中 d p [ i − k 1 ] [ j − k 2 ] dp[i-k_{1}][j-k_{2}] dp[i−k1][j−k2] 是各个决策， w ( i , j ) w(i,j) w(i,j) 是决策造成的影响。
主要还是看题目，没什么理论和模板。
DP例题
例题 1 1 1：
P1095 [NOIP2007 普及组] 守望者的逃离
首先，闪现的速度肯定比跑步快。所以可以有闪现先用闪现，没闪现就原地等待回复魔法。
当然，有的时候跑步会比回复魔法后闪现更快，所以可以先按照上述规则计算一遍，然后直接在计算好的 d p dp dp 数组里比较是否跑步会更快一些。
此题的教训： d p dp dp 并不是一定要一次求完，可以通过多次迭代最终求出结果。
#include <bits/stdc++.h>
using namespace std;
int m,s,t,f[300010],maxn=-99999999;
int main()
{scanf("%d%d%d",&m,&s,&t);for(int i=1;i<=t;i++){if(m>=10)f[i]=f[i-1]+60,m-=10;else f[i]=f[i-1],m+=4;}for(int i=1;i<=t;i++){if(f[i-1]+17>=f[i])f[i]=f[i-1]+17;if(f[i]>=s){printf("Yes\n%d",i);return 0;}maxn=max(maxn,f[i]);}printf("No\n%d",maxn);return 0;
}
例题 2 2 2：
P1004 [NOIP2000 提高组] 方格取数
由于两次纸条的传递互相影响，所以必须把两张纸条同时传递，每次两张纸条各传递一步，保证无后效性。
我们可以设置状态为两张纸条的位置，分别讨论每一步每一张纸条的传递情况，得到状态转移方程：
d p [ i ] [ j ] [ k ] [ l ] = max ( max ( d p [ i − 1 ] [ j ] [ k − 1 ] [ l ] , d p [ i − 1 ] [ j ] [ k ] [ l − 1 ] ) , max ( d p [ i ] [ j − 1 ] [ k − 1 ] [ l ] , d p [ i ] [ j − 1 ] [ k ] [ l − 1 ] ) ) + c [ i ] [ j ] + c [ k ] [ l ] dp[i][j][k][l]=\max(\max(dp[i-1][j][k-1][l],dp[i-1][j][k][l-1]),\max(dp[i][j-1][k-1][l],dp[i][j-1][k][l-1]))+c[i][j]+c[k][l] dp[i][j][k][l]=max(max(dp[i−1][j][k−1][l],dp[i−1][j][k][l−1]),max(dp[i][j−1][k−1][l],dp[i][j−1][k][l−1]))+c[i][j]+c[k][l]
由乘法原理，每次可以由 2 × 2 = 4 2\times2=4 2×2=4 中状态转移过来。
时间复杂度： O ( n 2 m 2 ) O(n^2m^2) O(n2m2)
此题的教训：遇到困难不应该放弃，而是应该增加维度。
#include <bits/stdc++.h>
using namespace std;
int n;
long long f[12][12][12][12],map1[12][12];
long long a,b,c,ans=0;
int main()
{scanf("%d",&n);scanf("%lld%lld%lld",&a,&b,&c);while(!(a==0&&b==0&&c==0)){map1[a][b]=c;scanf("%lld%lld%lld",&a,&b,&c);}for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)for(int k=1;k<=n;k++)for(int l=1;l<=n;l++){f[i][j][k][l]=max(max(f[i-1][j][k-1][l],f[i-1][j][k][l-1]),max(f[i][j-1][k-1][l],f[i][j-1][k][l-1]))+map1[i][j]+map1[k][l];if(i==k&&j==l)f[i][j][k][l]-=map1[i][j];}printf("%lld\n",f[n][n][n][n]);return 0;
}
更进一步的，我们可以优化掉一维：
d p [ k ] [ i ] [ j ] = max ( max ( d p [ k − 1 ] [ i ] [ j ] , d p [ k − 1 ] [ i − 1 ] [ j ] ) , max ( d p [ k − 1 ] [ i ] [ j − 1 ] , d p [ k − 1 ] [ i − 1 ] [ j − 1 ] ) ) + c [ i ] [ k − i ] + c [ j ] [ k − j ] dp[k][i][j]=\max(\max(dp[k-1][i][j],dp[k-1][i-1][j]),\max(dp[k-1][i][j-1],dp[k-1][i-1][j-1]))+c[i][k-i]+c[j][k-j] dp[k][i][j]=max(max(dp[k−1][i][j],dp[k−1][i−1][j]),max(dp[k−1][i][j−1],dp[k−1][i−1][j−1]))+c[i][k−i]+c[j][k−j]
因为两张纸条是同时传递的，而每次传递，不是横坐标加 1 1 1，就是纵坐标加 1 1 1，所以其实两张纸条的横纵坐标之和是相同的，也正好等于步数。所以可以用步数分别减去两张纸条的横坐标，就能求出纵坐标。
时间复杂度： O ( ( n + m ) n 2 ) O((n+m)n^2) O((n+m)n2)
例题 3 3 3：
P1006 [NOIP2008 提高组] 传纸条
同例题 2 2 2，注意循环顺序与最终状态的问题。
#include <bits/stdc++.h>
using namespace std;
int n,m;
long long f[60][60][60][60],map1[60][60];
long long a,b,c,ans=0;
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%lld",&map1[i][j]);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)for(int k=n;k>=1;k--)for(int l=m;l>=1;l--){f[i][j][k][l]=max(max(f[i-1][j][k-1][l],f[i-1][j][k][l-1]),max(f[i][j-1][k-1][l],f[i][j-1][k][l-1]))+map1[i][j]+map1[k][l];if(i==k&&j==l){f[i][j][k][l]-=map1[k][l];}}printf("%lld\n",f[n][m][n][m]);return 0;
}
例题 4 4 4：
P1541 [NOIP2010 提高组] 乌龟棋
由于每张卡牌只能用一次，如果设计带有当前位置的状态会有后效性。所以换一个思路，由于只有 4 4 4 种卡牌，且每张卡牌都数量不多（不会超过 40 40 40），所以可以考虑设状态 d p [ i ] [ j ] [ k ] [ l ] dp[i][j][k][l] dp[i][j][k][l] 为使用了 i i i 张 1 1 1 步的， j j j 张 2 2 2 步的， k k k 张 3 3 3 步的， l l l 张 4 4 4 步的后的最大得分。易得转移方程：
d = a [ i + j × 2 + k × 3 + l × 4 ] d=a[i+j\times2+k\times3+l\times4] d=a[i+j×2+k×3+l×4]
d p [ i ] [ j ] [ k ] [ l ] = max ( d p [ i − 1 ] [ j ] [ k ] [ l ] + d , max ( d p [ i ] [ j − 1 ] [ k ] [ l ] , max ( d p [ i ] [ j ] [ k − 1 ] [ l ] + d , f [ i ] [ j ] [ k ] [ l − 1 ] + d ) ) ) dp[i][j][k][l]=\max(dp[i-1][j][k][l]+d,\max(dp[i][j-1][k][l],\max(dp[i][j][k-1][l]+d,f[i][j][k][l-1]+d))) dp[i][j][k][l]=max(dp[i−1][j][k][l]+d,max(dp[i][j−1][k][l],max(dp[i][j][k−1][l]+d,f[i][j][k][l−1]+d)))
此题的教训：当一类状态不行时，应该改变状态的定义（或逆向思维），不要在一个错误的状态上耗费太多时间。
#include <bits/stdc++.h>
using namespace std;
int n,m,a[1000],b[1000],f[41][41][41][41],t[5];
int main()
{scanf("%d%d",&n,&m);for(int i=0;i<n;i++)scanf("%d",&a[i]);for(int i=0;i<m;i++){scanf("%d",&b[i]); t[b[i]]++;}f[0][0][0][0]=a[0];for(int i=0;i<=t[1];i++)for(int j=0;j<=t[2];j++)for(int k=0;k<=t[3];k++)for(int l=0;l<=t[4];l++){if(i>0)f[i][j][k][l]=max(f[i][j][k][l],f[i-1][j][k][l]+a[i+j*2+k*3+l*4]);if(j>0)f[i][j][k][l]=max(f[i][j][k][l],f[i][j-1][k][l]+a[i+j*2+k*3+l*4]);if(k>0)f[i][j][k][l]=max(f[i][j][k][l],f[i][j][k-1][l]+a[i+j*2+k*3+l*4]);if(l>0)f[i][j][k][l]=max(f[i][j][k][l],f[i][j][k][l-1]+a[i+j*2+k*3+l*4]);}printf("%d",f[t[1]][t[2]][t[3]][t[4]]);return 0;
}
例题 5 5 5：
P1156 垃圾陷阱
规则类动态规划。
一个显然的贪心：在垃圾掉落下来时立即使用这个垃圾是最优的。
首先，把垃圾按照 t t t 递增排序。然后因为对于每个垃圾，都有堆或不堆两种情况，可以借助 【5】背包类型动态规划学习笔记 的思想，设状态 d p [ i ] [ j ] dp[i][j] dp[i][j] 表示第 i i i 个垃圾丢下时，卡门生命值为 j j j 时的最大高度。为了避免重复转移，将一个垃圾使用多次，可以用前面的状态更新后面的状态，得到转移方程：
d p [ i + 1 ] [ j + f i ] = max ( f [ i ] [ j ] , f [ i + 1 ] [ j + f i ] ) dp[i+1][j+f_i]=\max(f[i][j],f[i+1][j+f_i]) dp[i+1][j+fi]=max(f[i][j],f[i+1][j+fi])
d p [ i + 1 ] [ j ] = max ( d p [ i ] [ j ] + h i , f [ i + 1 ] [ j ] ) dp[i+1][j]=\max(dp[i][j]+h_i,f[i+1][j]) dp[i+1][j]=max(dp[i][j]+hi,f[i+1][j])
第一个式子是不堆，第二个式子是堆。
如果第一次有一个状态的值达到了 D D D，那么可以跳出去，并且是最优解，可以返回了。另外注意跳不出去时的处理。
此题的教训：警示后人（WA on #3）
#include <bits/stdc++.h>
using namespace std;
struct litter
{int t,f,h;
}a[111];
int d,g,f[111][4012],tol=10;
bool cmp(struct litter a,struct litter b)
{return a.t<b.t;
}int main()
{scanf("%d%d",&d,&g);for(int i=0;i<g;i++)scanf("%d%d%d",&a[i].t,&a[i].f,&a[i].h);for(int i=0;i<g;i++)for(int j=0;j<=3010;j++)f[i][j]=-99999999;sort(a,a+g,cmp);f[0][10]=0;for(int i=0;i<g;i++)for(int j=1;j<=3010;j++){if(j>=a[i].t)f[i+1][j+a[i].f]=max(f[i][j],f[i+1][j+a[i].f]);if(j>=a[i].t)f[i+1][j]=max(f[i][j]+a[i].h,f[i+1][j]);if(f[i+1][j]>=d&&j>=a[i].t){printf("%d\n",a[i].t);return 0;}}for(int i=0;i<g;i++)if(a[i].t<=tol)tol+=a[i].f;else break;printf("%d\n",tol);return 0;
}
例题 6 6 6：
P1736 创意吃鱼法
可以分为两类：对角线向左下的正方形和对角线向右下的正方形。
满足条件的边长为 k k k 正方形可以由与它对角线走向相同的满足条件的边长为 k − 1 k-1 k−1 正方形转移过来。所以设状态 d p [ i ] [ j ] dp[i][j] dp[i][j] 为以 ( i , j ) (i,j) (i,j) 为顶点，满足条件的最大正方形的边长。
转移时还有一个额外要求：边长为 k k k 正方形的最外层除顶点外，必须全部为 0 0 0，这样才能保证这个要求：
此正方形子矩阵的其他地方无鱼
由于边长为 k − 1 k-1 k−1 正方形其他地方无鱼，而边长为 k k k 正方形的最外层除顶点外，全部为 0 0 0，此正方形子矩阵的其他地方依旧无鱼。
可以预处理出上，左，右三边连续的 0 0 0 的个数，在计算时就可以直接使用这些值。
两个转移方程：（仅在 1 1 1 处转移）
d p [ i ] [ j ] = min ( d p [ i − 1 ] [ j − 1 ] , min ( g [ i − 1 ] [ j ] , h [ i ] [ j − 1 ] ) ) + 1 dp[i][j]=\min(dp[i-1][j-1],\min(g[i-1][j],h[i][j-1]))+1 dp[i][j]=min(dp[i−1][j−1],min(g[i−1][j],h[i][j−1]))+1
d p [ i ] [ j ] = min ( f [ i − 1 ] [ j + 1 ] , min ( g [ i − 1 ] [ j ] , y [ i ] [ j + 1 ] ) ) + 1 dp[i][j]=\min(f[i-1][j+1],\min(g[i-1][j],y[i][j+1]))+1 dp[i][j]=min(f[i−1][j+1],min(g[i−1][j],y[i][j+1]))+1
注意此处是取最小值，因为正方形的边长受最小值的制约。如果不取最小值，那么最小值之外的部分将无法保证满足条件。
此题的教训：适当的预处理可以有效降低复杂度。
#include <bits/stdc++.h>
using namespace std;
int n,m,g[2500][2500],h[2500][2500],y[2500][2500],f[2500][2500],ans=0;
bool map1[2500][2500];
int main()
{scanf("%d%d",&n,&m);for(int i=0;i<n;i++)for(int j=0;j<m;j++)scanf("%d",&map1[i][j]); for(int i=0;i<m;i++)if(!map1[0][i])g[0][i]=1;for(int i=1;i<n;i++)for(int j=0;j<m;j++)if(!map1[i][j])g[i][j]=g[i-1][j]+1;for(int i=0;i<n;i++)if(!map1[i][0])h[i][0]=1;for(int i=0;i<n;i++)for(int j=1;j<m;j++)if(!map1[i][j])h[i][j]=h[i][j-1]+1;for(int i=0;i<m;i++)if(map1[0][i])f[0][i]=1;for(int i=0;i<n;i++)if(map1[i][0])f[i][0]=1; for(int i=1;i<n;i++)for(int j=1;j<m;j++)if(map1[i][j])f[i][j]=min(f[i-1][j-1],min(g[i-1][j],h[i][j-1]))+1;for(int i=1;i<n;i++)for(int j=1;j<m;j++)ans=max(ans,f[i][j]);for(int i=0;i<n;i++)if(!map1[i][m-1])y[i][m-1]=1;for(int i=0;i<n;i++)for(int j=m-2;j>=0;j--)if(!map1[i][j])y[i][j]=y[i][j+1]+1;memset(f,0,sizeof(f));for(int i=0;i<m;i++)if(map1[0][i])f[0][i]=1;for(int i=0;i<n;i++)if(map1[i][0])f[i][0]=1; for(int i=1;i<n;i++)for(int j=m-2;j>=0;j--)if(map1[i][j])f[i][j]=min(f[i-1][j+1],min(g[i-1][j],y[i][j+1]))+1;for(int i=0;i<n;i++)for(int j=0;j<m;j++)ans=max(ans,f[i][j]);printf("%d",ans);return 0;
}
例题 7 7 7：
P1133 教主的花园
之所以放在例题 7 7 7 ，是因为此题我的做法存疑。
参考 这篇题解 。
做法是类似破环成链，然后线性DP做。但是博客底下的评论：
请问这样不就相当于1和2断开了吗？
自己思考了一下好像有道理，但是先写着。
#include <bits/stdc++.h>
using namespace std;
long long n,a[100010][3],f[100010][3][2],ans=0;
int main()
{scanf("%lld",&n);scanf("%lld%lld%lld",&a[n-1][0],&a[n-1][1],&a[n-1][2]);for(int i=0;i<n-1;i++)scanf("%lld%lld%lld",&a[i][0],&a[i][1],&a[i][2]);for(int i=0;i<3;i++)a[n][i]=a[0][i];for(int i=0;i<n;i++)for(int j=0;j<3;j++)for(int k=0;k<2;k++)f[i][j][k]=-(long long)99999999999;for(int i=0;i<3;i++)for(int j=0;j<2;j++)f[0][i][j]=a[0][i];for(int i=1;i<n;i++)for(int j=0;j<3;j++){for(int k=0;k<j;k++)f[i][j][0]=max(f[i-1][k][1]+a[i][j],f[i][j][0]);for(int k=j+1;k<3;k++)f[i][j][1]=max(f[i-1][k][0]+a[i][j],f[i][j][1]);}for(int i=0;i<3;i++)for(int j=0;j<2;j++)ans=max(f[n-1][i][j],ans);printf("%lld",ans);return 0;
}
我认为的正解 这里
后记
DP好难啊…
愿天堂没有DP。
