问题描述
设有N*N的方格图(N<=10,我们将其中的某些方格中填入正整数,而其他的方格中则放入数字0。如下图所示(见样例)：
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
|
0
|
0
|
13
|
0
|
0
|
6
|
0
|
0
|
|
0
|
0
|
0
|
0
|
7
|
0
|
0
|
0
|
|
0
|
0
|
0
|
14
|
0
|
0
|
0
|
0
|
|
0
|
21
|
0
|
0
|
0
|
4
|
0
|
0
|
|
0
|
0
|
15
|
0
|
0
|
0
|
0
|
0
|
|
0
|
14
|
0
|
0
|
0
|
0
|
0
|
0
|
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
某人从图的左上角的A 点出发，可以向下行走，也可以向右走，直到到达右下角的B点。在走过的路上，他可以取走方格中的数(取走后的方格中将变为数字0)。
此人从A点到B 点共走两次，试找出2条这样的路径，使得取得的数之和为最大。
输入
输入的第一行为一个整数N(表示N*N的方格图)，接下来的每行有三个整数，前两个表示位置，第三个数为该位置上所放的数。一行单独的0表示输入结束。
输出
只需输出一个整数，表示2条路径上取得的最大的和。
样例 ：
输入
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
输出
67
*********************************************************************
解析：
该类型的题我看了很多题解，其中有人是先dfs再动规，但大多数人还是用多线程dp做的，即定义一个三维数组dp[k][i][j](其中k表示走了k步，i表示第一个人在i行，j表示第二个人在j行，这样就可以得出第一个人在k-i+1列，第二个人在k-j+1列)。
这里为了防止两个人所走路径的混乱交叉，我们规定第2个人走在第1个人的前面，当两个人走到同一个位置时，只加一个方格数的元素，当走到不同的方格时，则加上两个方格的元素。当走到该方格时，每个人最多有两种选择走的这个方格。
*********************************************************************
1 #include<iostream> 2 #include<cstdio> 3 #include<string> 4 #include<cstring> 5 using namespace std; 6 7 int n,num[150][50][50],map[50][50],i,j,k;//变量常量说明 8 int max(int a,int b)//比较函数 9 { 10 return a>b?a:b; 11 } 12 int max(int a,int b,int c,int d)//比较函数 13 { 14 int m=a; 15 if(m<b)m=b; 16 if(m<c)m=c; 17 if(m<d)m=d; 18 return m; 19 } 20 void init()//初始化函数 21 { 22 cin>>n; 23 memset(map,0,sizeof(map)); 24 while(cin>>i>>j>>k&&i&&j&&k) 25 { 26 map[i][j]=k; 27 } 28 29 30 } 31 void dp()//dp 32 { 33 memset(num,0,sizeof(num)); 34 for(k=1;k<=2*n-1;k++) 35 for(i=(k<n?0:k+1-n);i<=k&&i<=n;i++)//这里做一下判断，防止列越界 36 for(j=i;j<=k&&j<=n;j++)//第二个人在第一个人的前方（防止路径交叉） 37 { 38 if(i==0&&j==0)num[k][i][j]=num[k-1][i][j];//只有一种选择 39 else if(i==0&&j==k)num[k][i][j]=num[k-1][i][j-1];//只有一种选择 40 else if(i==0&&j!=k)num[k][i][j]=max(num[k-1][i][j-1],num[k-1][i][j]);//第二个人有两种选择 41 else if(i>0&&j==k)num[k][i][j]=max(num[k-1][i-1][j-1],num[k-1][i][j-1]);//第1个人有两种选择 42 else num[k][i][j]=max(num[k-1][i-1][j-1],num[k-1][i][j-1],num[k-1][i-1][j],num[k-1][i][j]);//都有两种选择 43 if(j==i) num[k][i][j]+=map[i][k-i+1];//两人同时走到一个位置 44 if(j!=i) num[k][i][j]+=map[i][k-i+1]+map[j][k-j+1];//两个走到不同的位置 45 } 46 cout<<num[2*n-1][n][n]<<endl; 47 } 48 int main()//主函数 49 { 50 //freopen("fgqs.in","r",stdin); 51 //freopen("fgqs.out","w",stdout); 52 init(); 53 dp(); 54 return 0; 55 }