数字三角形的拓展题
AcWing 1015. 摘花生
不同点:
1.数字三角形的那道题目需要给第一个值赋上初值,以及最后的答案,是在最后一行中的最大值
2.这个题目只需要直接判断两个方向的最值即可,而且由于下标是从1开始的因此,边界情况不需要判断
#include<iostream>
using namespace std;
const int N = 110;
int g[N][N],n,m;
int f[N][N];
int main()
{
int T;
cin >> T;
while(T--)
{
cin >> n >> m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin >> g[i][j];
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])+g[i][j];
cout << f[n][m] << endl;
}
return 0;
}
二.AcWing 1018. 最低通行费
这个题和以上两个题都不同,但是思路类似,都是从左上角走到右下角
不同点:求的是最小值,因此在给数组赋初始值的时候不能是0,否则在最左边时,按照之前的枚举的话会导致从最左边走到目标点的话,值会最小——导致在后面的一系列计算中都发生错误——因此可以给他赋上一个足够大的初始值
#include<iostream>
#include<cstring>
using namespace std;
const int N = 110;
int f[N][N],w[N][N];
int n;
int main()
{
cin >> n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin >> w[i][j];
memset(f,0x3f,sizeof f);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i==1&&j==1)f[i][j]=w[i][j];(第一个点需要特判,一般需要赋值的点都可以按照实际情况来计算)
else
f[i][j]=min(f[i-1][j],f[i][j-1])+w[i][j];
cout << f[n][n] << endl;
}
三.AcWing 1027. 方格取数
不同点:
1.出发点变成了两个
2.第一次走过的点,第二次走的话会显示获得的点数为0
思路:两个点同时走然后一起到达最右下角
f[i1][j1][i2][j2]——由于是一起走的因此,无论如何i1+j1=i2+j2,此时可以将四维优化为三维
知道i1+j1,那么只需要知道i1,i2就可以知道走到了那个点。f[k][i1][i2]表示走到某一点(i1,k-i1)与(i2,k-i2)的最大值。再分别枚举最后一步是怎样走到的,比如都是通过向下走或者向右走,再在这些情况中取一个max,最后求出最大值
#include<iostream>
using namespace std;
const int N = 30;
int n;
int f[N][N][N];
int w[N][N];
int a,b,c;
int main()
{
cin >> n;
while(cin >> a >> b >> c,a||b||c)w[a][b]=c;
for(int k=2;k<=n*2;i++)
for(int i1=1;i1<=n;i1++)
for(int i2=1;i2<=n;i2++)
{
int j1=k-i1,j2=k-i2;
if(j1>=1&&j1<=n&&j2>=1&&j2<=n)
{
int &x=f[k][i1][i2],t=w[i1][j1];
if(i1!=i2)t+=w[i2][j2];
//避免重复计算,由于第二次计算的话,值会更新为0
x=max(x,f[k-1][i1][i2]+t);
x=max(x,f[k-1][i1-1][i2]+t);
x=max(x,f[k-1][i1-1][i2-1]+t);
x=max(x,f[k-1][i1][i2-1]+t);
}
}
cout << f[n*2][n][n] << endl;
return 0;
}
AcWing 275.
与上一个题不同:两个点的状态发生了改变,一个从左上角,一个是在右下角
其实可以转换为上一个题,只需要将末状态与初始状态交换一下即可,并不影响结果的正确性——路径没发生改变
#include<iostream>
#include<cstring>
using namespace std;
const int N = 60;
int w[N][N];
int f[N*2][N][N];
int n,m;
int main()
{
cin >> n >> m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin >> w[i][j];
for(int k=2;k<=n+m;k++)
for(int i1=1;i1<=n;i1++)
for(int i2=1;i2<=n;i2++)
{
int j1=k-i1,j2=k-i2;
if(j1>=1&&j1<=m&&j2>=1&&j2<=m)
{
int &x = f[k][i1][i2],t= w[i1][j1];
if(i1!=i2)t+=w[i2][j2];
x=max(x,f[k-1][i1-1][i2]+t);
x=max(x,f[k-1][i1][i2]+t);
x=max(x,f[k-1][i1][i2-1]+t);
x=max(x,f[k-1][i1-1][i2-1]+t);
}
}
cout << f[n+m][n][n] << endl;
return 0;
}