题目描述
设有 N×N 的方格图,我们在其中的某些方格中填入正整数,而其它的方格中则放入数字0。
某人从图中的左上角A出发,可以向下行走,也可以向右行走,直到到达右下角的 B 点。
在走过的路上,他可以取走方格中的数(取走后的方格中将变为数字0)。
此人从A点到B点共走了两次,试找出两条这样的路径,使得取得的数字和为最大。
输入格式
第一行为一个整数N,表示 N×N 的方格图。
接下来的每行有三个整数,第一个为行号数,第二个为列号数,第三个为在该行,该列上所放的数.
行和列编号分别从1,1开始。
一行“0 0 0”表示结束。
输出格式
输出一个整数,表示两条路径上取得的最大的和
数据范围
N<=10
样例
8
2 3 13
2 6 6
3 5 7
4 4 14
5 2 21
5 6 4
6 3 15
7 2 14
0 0 0
思路
因为两条路线格子数只能取一次,只走一次走不完。
f[i1][j1][i2][j2]:表示所有从(1,1),(1,1)
分别走到(i1,j1),(i2,j2)的路径
属性:max
因为两条路线从左上角走到右下角,而且它们只
能向下或者向右走那么它们所走的步数是一样的
那么我们可以把k来代替步数
k=i1+j1=i2+j2(即k是两条路线的横纵坐标之和)
而且只有i1+j1=i2+j2,两条路径的格子才有可能重合
这样把状态量从四维降到三维,从而降低了时间复杂度
状态表示:
集合:f[k][i1][i2]:所有从(1,1),(1,1)分别
走到(i1,k-i1),(i2,k-i2)的路径
属性:max
状态计算:
下面中的下是最后一步是往下走,右同理
t是格子数之和
1:下下,f[k-1][i1-1][i2-1]+t
2:下右,f[k-1][i1-1][i2]+t
3:右下,f[k-1][i1][i2-1]+t
4:右右,f[k-1][i1][i2]+t
f[k][i1][i2]=max(1,2,3,4)
#include <bits/stdc++.h>
using namespace std;
const int N=15;
int f[2*N][N][N],w[N][N];
int main(){
int n;
cin>>n;
int a,b,c;
while(cin>>a>>b>>c,a||b||c)
w[a][b]=c;
for(int k=2;k<=2*n;k++)
for(int i1=1;i1<=n;i1++)
for(int i2=1;i2<=n;i2++){
int j1=k-i1;
int j2=k-i2;
if(1<=j1&&j1<=n&&
1<=j2&&j2<=n){
int t=w[i1][j1];
if(i1!=i2)
t+=w[i2][j2];
int &x=f[k][i1][i2];
x=max(x,f[k-1][i1-1][i2-1]+t);
x=max(x,f[k-1][i1-1][i2]+t);
x=max(x,f[k-1][i1][i2-1]+t);
x=max(x,f[k-1][i1][i2]+t);
}
}
cout<<f[2*n][n][n];
return 0;
}