算法打铁录

算法打铁录

数字三角形模型（格子取数模型）

上题便是格子取数模型的模板题，假设两个人从左上角同时走两条路线到右下角，取走路径上的格子数，且格子中的数只能取一次。

由于两人是同时走路径，所以两人的横纵坐标之和必相等。我们可以设为k，假设此时分别到达了(i1,,j1)以及(i2,j2)两点，代入k可得两个点为(i1,k-i1)以及(i2,k-i2)，i1和i2可以相等或者不相等，如果相等，那么这个格子里的数字只能取一次，如果不相等，那就可以取到两个不一样的数了，而且要注意是对每个路径上的点都这样做！！！这才是DP的重点。

也就是说假设现在两条路径到了同一个点，假设两条路径都是从上往下的，那么上一个点必然也是同一个点，那么这个上一个点是不用再考虑的，因为这个点已经在递推中被考虑过了。

具体过程由于两条路径在每个点各有两种情况，从上往下或者从左往右，所以有四种情况。

且终点重合只加一次，不重合加两个值，之后四种情况取最大值就可以了。具体递推参考下图。

    DP需要建立一个三维矩阵来求解，如上图所示，三维矩阵值的下标为0的地方同样空出来，主体代码下标从1开始，下标是0的地方取0，由于是最大值问题，这样边界值就不会出错。

     代码如下。

#include<iostream>
using namespace std;
const int N=20;
int array[N][N];
int result[2*N][N][N];
int main()
{int n;cin>>n;int a,b,c;while(cin>>a>>b>>c && a||b||c){array[a][b]=c;}for(int k=2;k<=n+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(j1>=1&&j1<=n&&j2>=1&&j2<=n){int& x=result[k][i1][i2];int t=array[i1][j1];if(i1!=i2)t+=array[i2][j2];x=max(x, result[k-1][i1-1][i2-1]+t);x=max(x, result[k-1][i1-1][i2]+t);x=max(x, result[k-1][i1][i2-1]+t);x=max(x, result[k-1][i1][i2]+t);}}}}cout<<result[2*n][n][n];return 0;
}