题目：方格取数 拓展题：传纸条 题目大意：给定一个矩阵每一个位置有一个权值，从左上角到右下角，要走两次，所到的点如果有权值就取出并变为0，求所走路线取值和最大值。 解题思路：dp算法
首先假设两条路同时出发，如果相遇在同一个各自就只需要取一次权值。 这里我们来考虑状态：k表示当前所在位置步数（下标和，即x+y），i1表示第一条路线所在位置的行，i2表示第二条路线当前所在位置的行,即dp[k][i][j]。 因为判断是否在同一个位置的条件就是步数（下标和）相同的请情况下，两条路线在同一行，那么必定在同一列。 现在来考虑状态转移：每一条路线的每一个位置都可以会从他的上方或者他的左边取过来，因为有两条路所以就会有4个状态转移。上代码：
#include<bits/stdc++.h> using namespace std; const int N=27; int w[N][N],dp[N][N][N];//dp[k][i1][i2]表示在k步数下，第一条路线所在行i1，第二条路线所在行i2 int main(){ int n,a,b,c; cin>>n; while(cin>>a>>b>>c,a||b||c){//输入数据 w[a][b]=c; } for(int k=2;k<=n+n;k++){//k的取值为2开始，到n+n，因为起点从（1，1）开始，终点为（n,n） for(int i1=1;i1<=n;i1++){//枚举每一步数下，第一条路所在行 for(int i2=1;i2<=n;i2++){//枚举每一步数下，第二条路所在行 int j1=k-i1,j2=k-i2,t=w[i1][j1];//可由步数和所在行，求出他们所在的列，t为第一条路线所在位置(i1,j1)的权值 if(j1>=1&&j1<=n&&j2>=1&&j2<=n){//判断所在位置是否合法 if(i1!=i2)t+=w[i2][j2];//如果不在同一个位置（就加上第二条路上所在位置(i2,j2)的权值） //以下为状态转移 dp[k][i1][i2]=max(dp[k][i1][i2],dp[k-1][i1-1][i2-1]+t); //当前这一步可以由上一步时，第一条路线所在位置的左边，第二条路线所在位置的左边转移过来。 dp[k][i1][i2]=max(dp[k][i1][i2],dp[k-1][i1-1][i2]+t); //当前这一步可以由上一步时，第一条路线所在位置的左边，第二条路线所在位置的上边转移过来。 dp[k][i1][i2]=max(dp[k][i1][i2],dp[k-1][i1][i2-1]+t); //当前这一步可以由上一步时，第一条路线所在位置的上边，第二条路线所在位置的左边转移过来。 dp[k][i1][i2]=max(dp[k][i1][i2],dp[k-1][i1][i2]+t); //当前这一步可以由上一步时，第一条路线所在位置的上边，第二条路线所在位置的上边转移过来。 //因为k-1表示为上一步，i1，i2不变可表示上一个位置的j1,j2 } } } } cout<<dp[n+n][n][n]<<endl;//最终状态存放在终点第一条路在n行，，第二条路在n行。 return 0; }