洛谷P1004方格取数

洛谷P1004方格取数(双向dp)

题目描述：设有N×N的方格图(N≤9)，我们将其中的某些方格中填入正整数，而其他的方格中则放入数字0。如下图所示（见样例）:

 A
  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
                          B

某人从图的左上角的A点出发，可以向下行走，也可以向右走，直到到达右下角的B点。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。 此人从A点到B点共走两次，试找出2条这样的路径，使得取得的数之和为最大。

输入输出格式

输入格式：

输入的第一行为一个整数N（表示N×N的方格图），接下来的每行有三个整数，前两个表示位置，第三个数为该位置上所放的数。一行单独的0表示输入结束。

输出格式：

只需输出一个整数，表示2条路径上取得的最大的和。

输入输出样例

输入样例#1：

 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

输出样例#1：

 67

代码如下：

 #include<iostream>
 #include<cstdio>
 #include<algorithm>
 using namespace std;
 ​
 int n,m;//m是为了记录有几个元素不为零 
 int map[10][10];
 int f[11][11][11][11];
 //int maxv;
 struct point{
     int x;
     int y;
     int data;
 }p[100];
 int main(){
     scanf("%d",&n);//代表n*n的方格矩阵 
     
     int a,b,c;
     while(true){
         scanf("%d%d%d",&a,&b,&c);
         if(!a&&!b&&!c)
             break;
         p[++m].x = a;
         p[m].y = b;
         p[m].data = c;//把不为零的元素信息全部存放入point数组p中 
     }
     //还要将p中的信息写入地图中,此时p中有m个元素
     for(int i=1;i<=m;i++){
         map[p[i].x][p[i].y] = p[i].data;
     } 
     //四维dp
     for(int i=1;i<=n;i++){
         for(int j=1;j<=n;j++){
             for(int k=1;k<=n;k++){
                 for(int l=1;l<=n;l++){
                     f[i][j][k][l]=max(f[i-1][j][k-1][l],
                     max(f[i-1][j][k][l-1],
                     max(f[i][j-1][k-1][l],
                     f[i][j-1][k][l-1])))
                     +map[i][j]+map[k][l];
                     
                     if(i==k&&j==l)
                         f[i][j][k][l]-=map[i][j];
                 }
             }
         }
     } 
     printf("%d",f[n][n][n][n]);
     return 0;
 } 

分析：两次取数可以同时进行，这是就需要采用双dp，创建一个f数组，前二维用来描述第一次取数从(1,1)->(i,j)，后二维用来描述第二次取数从(1,1)-(k,l)，题中要求的是两次之和最大，第一次的状态是由[i-1] [j] 、[i] [j-1]两个方向转移而来，第二次的状态是由[k-1] [l] 、[k] [l-1]两个方向转移而来，所以，两次组合就有2*2种，也就是有四种可能的状态来转移到[i] [j] [k] [l].这是我们就要比较这四种组合来取得最大的方案，并加上(i,j)和(k,l)点的value。如果这时(i,j)=(k,l),我们就要减去一个value，因为数被取走后该位置就为零了，会重复加一个。

 

运行结果如图：