这个模型涉及到的就是简单的与路径有关的状态转移,最简单的应用就是求路径上的最大和,只用每个状态可以由哪些状态转移来即可。
例1:
摘花生
思路:这道题看上去是网格图,但它只能向东和向南走,也就是说,每个点只能由它上面或者左边的点走到,那么我们只用从这两个中取一个大的来更新当前点状态即可。
我们还是按照闫式dp法来分析一下:
首先定义状态表示:dp[i][j]表示所有走到坐标(i,j)时的路径和的集合,值表示当中的最大值,
状态计算:当前状态只能由左边和上面两个状态转移而来,那么就是f[i][j]=max(f[i-1][j],f[i][j-1])+a[i][j];
另外我们多加一个边界值初始化考虑:
因为取最大值,所以边界值为0的时候不会影响我们的计算,它不会被取进去,故而无所谓。
#include<bits/stdc++.h>
using namespace std;
int a[200][200],f[200][200];
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++) scanf("%d",&a[i][j]);
}
memset(f,0,sizeof f);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
f[i][j]=max(f[i-1][j],f[i][j-1])+a[i][j];
}
}
cout<<f[n][m]<<endl;
}
}
例2
最低通行费
思路:同样是很裸的题目,唯一的区别是这里将行走方向的限定给得很有趣,“每穿越中间1个小方格,都要花费1个单位时间。商人必须在 (2N−1)个单位时间穿越出去。”我们沿边界走一下就会发现时间刚好是2n-1,所以很明显题目的意思就是不能走回头路,也就是只能向右或者向下走,那么跟上题几乎一样,唯一的区别就是这道题需要的是最小值,所以边界为0是会影响min()取值的,那么我们将结果数组初始化为正无穷即可。另外要注意,这时候f[1][1]需要手动赋,因为赋完所有的地方都是正无穷。
#include<bits/stdc++.h>
using namespace std;
int a[200][200],f[200][200];
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++) scanf("%d",&a[i][j]);
memset(f,0x3f,sizeof f);
f[1][1]=a[1][1];
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i!=1||j!=1)f[i][j]=min(f[i-1][j],f[i][j-1])+a[i][j];
}
}
cout<<f[n][n];
}
例3:
方格取数
思路:这道题就更有意思了,要求的是两条路径的最大值,显然我们不能将两条路径分开算,因为每个数被取后,该方格变成0,我们在dp统计的过程中去标记哪些被访问过是很麻烦的事情(感觉需要记录每个状态是由谁转移来的,然后倒序遍历这条路,将遍历到的点标记。突然感觉这个思路好像能实现,不过两次dp而已,等等,这样代码量就上去了,感觉有点不划算,而且最优路径可能是两条路径分开都不是最优的,但合起来是,所以没必要。),而且两条路径会相互影响,所以我们直接将两条路径一块儿讨论,最关键的问题就是两条路径会相交,那么它们什么时候会相交呢,我们可以发现只有当x1+y1==x2+y2时会相交,那么我们定义一个变量来储存横纵坐标的和就可以将
我们先来按照闫式dp法简单讨论一下:dp[i1][j1][i2][j2]表示1走到(i1,j1),2走到(i2,j2)时的最大值,这个值能由四个状态转移而来:1上2上,1左2左,1上2左,1左2上,但是要注意到这里这么讨论的话,四重循环太大了,我们优化掉一维,用一个变量k来表示两者横纵坐标和,我们最终都要走到(n,n)位置,而且两个人同时走,那么横纵坐标实际上和应该相同。那么就刚好。
那就是用dp[k][i][j]来表示横纵坐标和为k,1走到i,2走到j时的最大值。
状态转移,想要转移首先要清楚这个此时的坐标是否合法,i,j有范围限定肯定没问题,但是y1,y2可不能保证,所以要先算出来然后判断一下。
如果合法,那么我们就开始转移,肯定是要考虑上一步的位置,而且是要考虑两者的上一步:
1上2上:f[k-1][i-1][j-1]
1左2左:f[k-1][i][j]//从左边来i,j的坐标自然不变
1上2左:f[k-1][i-1][j]
1左2上:f[k-1][]i[j-1]
另外还要注意,当前的i,j有相交的可能,我们要加个特判,因为如果相交就只能将g[i][y1]取一次,否则是可以取g[i][y1]和g[j][y2]的;
#include<bits/stdc++.h>
using namespace std;
int g[100][100],f[100][100][100];
int main()
{
int n;
scanf("%d",&n);
int a,b,c;
while(~scanf("%d%d%d",&a,&b,&c))
{
if(a==b&&b==c&&!c) break;
g[a][b]=c;
}
for(int k=2;k<=n+n;k++)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
int y1=k-i,y2=k-j;
if(1<=y1&&y1<=n&&1<=y2&&y2<=n)
{
int t=g[i][y1];
if(i!=j||y1!=y2) t += g[j][y2];
int m=0;
m=max(f[k-1][i-1][j-1],f[k-1][i-1][j]);
m=max(m,f[k-1][i][j-1]);
m=max(m,f[k-1][i][j]);
f[k][i][j]=m+t;
}
}
}
}
cout<<f[n+n][n][n];
}
例4
传纸条
思路:这道题虽然问的是正反两条路径,但实际上还是两条路径求最大值,因为反着的那条路径实际上正着也能走,所以它跟方格取数并无不同,就方格取数的代码稍微改改就行了。
#include<bits/stdc++.h>
using namespace std;
int g[200][200],f[200][200][200];
int main()
{
int n,m;
scanf("%d%d",&m,&n);
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++) scanf("%d",&g[i][j]);
}
for(int k=2;k<=n+m;k++)
{
for(int i=1;i<=m;i++)
{
for(int j=1;j<=m;j++)
{
int y1=k-i,y2=k-j;
if(1<=y1&&y1<=n&&1<=y2&&y2<=n)
{
int t=g[i][y1];
if(i!=j||y1!=y2) t += g[j][y2];
int m=0;
m=max(f[k-1][i-1][j-1],f[k-1][i-1][j]);
m=max(m,f[k-1][i][j-1]);
m=max(m,f[k-1][i][j]);
f[k][i][j]=m+t;
}
}
}
}
cout<<f[n+m][m][m];
}
至此,数字三角形模型就讨论完了,实际上就两种,单路径和双路径,单路径就考虑上一步从哪里转移来的,双路径不用在意方向,因为这条路反着能走,正着自然也能走,那么我们实际上只用考虑两条正着的路即可,正着的路就多加一维状态,从坐标和角度来考虑就行。