动 态♂规 划 整 理
Dynamic Programming(DP)
动态规划刷题小结
例题1：乌龟棋
传送门：https://www.luogu.com.cn/problem/P1541
题目中先给出一个长度为\(n\)的序列(我们把它叫做序列\(g\))，其中\(g_i\)表示第\(i\)个格子的得分
另外，有四种卡片，每一种可以走不同的步数，当走到第\(i\)个格子，就能得到\(g_i\)的分数，求最大得分
本题数据范围较小\((\leq40)\)，我们根据DP的多一种状态升一维的原则，(反正数据范围小那我数组不是乱开吗qwq)，可以考虑开四维数组\(f[40][40][40][40]\)
于是，现在我们可以用\(f_{ijkl}\)表示第一、二、三、四种牌分别用了\(i、j、k、l\)张
注意到，第一、二、三、四种牌分别可以走\(1、2、3、4\)步，那么\(f_{ijkl}\)就表示当前在第\((i+2j+3k+4l)\)个格子的最大得分
题目中给出：我们可以直接获得\(g_1\)的分数，所以\(f_{0000}=g_1\)，这是我们的初始状态
现在考虑\(f_{ijkl}\)可以由哪些状态转移得到：
\( \begin{cases} if(i-1\geq 0) f_{(i-1)jkl}\rightarrow f_{ijkl}\\ \\ if(j-1\geq 0) f_{i(j-1)kl}\rightarrow f_{ijkl}\\ \\ if(k-1\geq 0) f_{ij(k-1)l}\rightarrow f_{ijkl}\\ \\ if(l-1\geq 0) f_{ijk(l-1)}\rightarrow f_{ijkl}\\ \end{cases} \)
其中，“\(\rightarrow\)”表示可以由前一种状态转移到后一种状态
可以发现，转移时就是相当于选了一张卡牌，我们用\(ovo\)表示转移后到了第\(ovo\)格，所以有\(ovo=i+2j+3k+4l\)
那么我们这次转移的新增得分也就是\(g_{ovo}\)了，现在我们用\(f_{ijkl}\)和转移之前的分数\(+g_{ovo}\)取\(max\)就得到了状态转移方程
下面是书面的状态转移方程：
\( \begin{cases} if(i-1\geq 0) f_{ijkl}=max(f_{ijkl},f_{(i-1)jkl})\\ \\ if(j-1\geq 0) f_{ijkl}=max(f_{ijkl},f_{i(j-1)kl})\\ \\ if(k-1\geq 0) f_{ijkl}=max(f_{ijkl},f_{ij(k-1)l})\\ \\ if(l-1\geq 0) f_{ijkl}=max(f_{ijkl},f_{ijk(l-1)})\\ \end{cases} \)
有了状态转移方程，代码就\(so easy\)了！！！
\(Code\)
#include
#include
const int maxn=45;
int f[maxn][maxn][maxn][maxn],g[355];
int n,m,a,b,c,d;
int main(){
scanf("%d%d",&n,&m);
for(int i=0;i 例题2：滑雪
传送门：https://www.luogu.com.cn/problem/P1434
本题正解是一个记忆化搜索，但是由于本人太蒻，不会记搜，只好用DP来做这个题
安利一下大佬的记搜题解叭：
题目中给出一个大小为\(rc\)的矩阵(我们叫它矩阵\(g\))，其中\(g_{ij}\)表示\((i,j)\)这个点的高度
要求也很简单，我们在只向上下左右四个方向走的情况下，求出最长下降的序列的长度
我们新建一个矩阵：\(f\)，用\(f_{ij}\)表示以\((i,j)\)为结尾的最长下降序列长度
现在考虑\(f_{ij}\)可以由哪些状态转移得到，：
\(
\begin{cases}
if(g_{ij}
可以发现，转移时就是从周围四个比较高的地方走到\(f_{ij}\)，那么新增的长度就是\(1\)
我们用\(f_{ij}\)和转移之前的长度\(+1\)再取\(max\)，就得到了状态转移方程：
\(
\begin{cases}
if(g_{ij}
但是，这个状态转移方程的条件是在计算\(f_{ij}\)之前，它周围比它高的格子已经被计算过了
那么解决这个问题的最简单的办法就是：直接\(DP\)\(nm\)遍，但是看到\(n\leq 100\)的范围，我就抱着试一试的心态上了
\(Code\)
#include
#include
#include
const int maxn=105;
int f[maxn][maxn],g[maxn][maxn],n,m,ans;
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
scanf("%d",&g[i][j]);
f[i][j]=1;
}
for(int k=1;k<=n*m;k++)//直接DPn*m遍
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
if(g[i][j] 其实这题数据出水了，结果这份\(O(n^2m^2)\)的代码勇夺90分\((Test #10 TLE)\)
现在考虑怎么优化：
首先，上面的这个思路的复杂度瓶颈就在于：为了解决上面标红的那个问题，我们进行了\(nm\)次\(DP\)，这导致了时间的浪费
我突然想到一个玄学做法：周围比它高的格子要先于他计算，那我从最高的格子开始高度依次递减DP不就得了！
于是要维护一个高度最大值和坐标，我又想到了\(priority\)_\(queue\)，这样时间复杂度猛降到大约\(O(nmlogn)\)
\(Code\)
#include
#include
#include
#include
const int maxn=105;
std::priority_queue< std::pair > >q;//pair套pair，第一个pair的第一维表示高度，维护最大高度，第二维的第一维表示横坐标，第二维表示纵坐标
int f[maxn][maxn],g[maxn][maxn],n,m,ans;
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0' || ch>'9'){ if(ch=='-') f=-1;ch=getchar();}
while(ch>='0' && ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return x*f;
}//乱写的快读
int main(){
n=read(),m=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
g[i][j]=read();
q.push(std::make_pair(g[i][j],std::make_pair(i,j)));//进入大根堆
f[i][j]=1;//所有点初始化为1(一个点就算不走，他自己就是1的长度)
}
while(q.size()!=0){//当大根堆不为空，循环DP
int height=q.top().first;
int row=q.top().second.first;
int line=q.top().second.second;
q.pop();
if(g[row][line] 事实上证明，这份代码跑的飞起
关于今天的\(DP\)刷题整理完成啦！\(OvO\)
PS：感谢您的阅读\(qwq\)