题目描述

设有 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;
}