题目描述
设有 N×N 的方格图,我们在其中的某些方格中填入正整数,而其它的方格中则放入数字0
某人从图中的左上角 A 出发,可以向下行走,也可以向右行走,直到到达右下角的 B 点。
在走过的路上,他可以取走方格中的数(取走后的方格中将变为数字0)。
此人从 A 点到 B 点共走了两次,试找出两条这样的路径,使得取得的数字和为最大。
输入格式
第一行为一个整数N,表示 N×N 的方格图。
接下来的每行有三个整数,第一个为行号数,第二个为列号数,第三个为在该行、该列上所放的数。
行和列编号从 11 开始。
一行“0 0 0”表示结束。
输出格式
输出一个整数,表示两条路径上取得的最大的和。
数据范围
N≤10
算法:线性DP
时间复杂度:O($N^2$)
按照之前的线性DP的思路可以进行类比f[i1][i2][j1][j2]分别表示第一次经过点(i1,j1)第二次经过(i2,j2)
属性:两次之和的最大值
但是题目中两次经过相同的点存在数值的变化,且若已知一个位置坐标之和和其中一个坐标,
那么另一个坐标就可以唯一的确定了,因此可以将状态表示简化成f[k][i1][i2],其中k是横纵坐标之和
需要注意
(1)起始位置:从(1,1)起始,故循环k从2开始
(2)判断两次是否经过相同的点:如果相同,第二次为0;不相同则将两次的价值全部加上
(3)实际存在i1 和 i2的枚举范围
for(int i1=max(1,k-n);i1<=min(k-1,n);i1++){
for(int i2=max(1,k-n);i2<=min(k-1,n);i2++){
(4)坐标从(1,1)开始,则不需要进行判断防止越界(因为0的这外面一层是越界的保护)
C++代码
#include<iostream>
#include<cstring>
using namespace std;
const int N=15;
int f[N*2-1][N][N];
int g[N][N];
int n;
int main()
{
cin>>n;
int r,c,x;
while(cin>>r>>c>>x,r || c|| x)g[r][c]+=x;
for(int k=2;k<=n*2;k++){
for(int i1=1;i1<=n;i1++){
for(int i2=1;i2<=n;i2++){
if(k==2)f[k][i1][i2]=g[1][1];
else{
int j1=k-i1,j2=k-i2;
int v=g[i1][j1];
if(j1!=j2)v+=g[i2][j2];
int & t=f[k][i1][i2];
//枚举四种途径 为了更清晰并跟之前的题目对齐 写出了限制条件
if(i1>=1 && i2>=1)t=max(t,f[k-1][i1-1][i2-1]+v);
if(i1>=1 && j2>=1)t=max(t,f[k-1][i1-1][i2]+v);
if(j1>=1 && i2>=1)t=max(t,f[k-1][i1][i2-1]+v);
if(j1>=1 && j2>=1)t=max(t,f[k-1][i1][i2]+v);
}
}
}
}
cout<<f[2*n][n][n]<<endl;
return 0;
}