dp4--codeVs1043 方格取数

一、心得

 

二、题目

1043 方格取数

 

2000年NOIP全国联赛提高组

 时间限制: 1 s

 空间限制: 128000 KB

 题目等级 : 钻石 Diamond

 查看运行结果

 

 

题目描述 

Description

设有N*N的方格图(N<=10,我们将其中的某些方格中填入正整数,而其他的方格中则放入数字0。如下图所示（见样例）：

 

某人从图的左上角的A 点出发，可以向下行走，也可以向右走，直到到达右下角的B点。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。

此人从A点到B 点共走两次，试找出2条这样的路径，使得取得的数之和为最大。

 

输入描述 

Input Description

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

输出描述 

Output Description

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

样例输入 

Sample Input

      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

样例输出 

Sample Output

      67

数据范围及提示 

Data Size & Hint

如描述

分类标签 Tags 

           

 

三、分析

* codeVs1043方格取数.cpp

* 分析：

* 把这个问题看成两个人同时走就ok了

* 状态：

* f[h1][w1][h2][w2]表示第一个人走到(h1,w1)位置和第二个人走到(h2,w2)位置所取的最大和

* 最终状态：

* f[n][n][n][n]

* 初始状态：

* f[0][0][0][0] （都没走的情况，这就是最初的情况）

* 只可能两个人同时走了或者没走，不可能一个人走了，一个人没走

*

* 状态转移方程：

* 走到(h1,w1)，(h2,w2)的四种方式：

* 1、都向下走 f[h1-1][w1][h2-1][w2]

* 2、都向右走 f[h1][w1-1][h2][w2-1]

* 3、第一个人向下，第二个人向右 f[h1-1][w1][h2][w2-1]

* 4、第一个人向右，第二个人向下 f[h1][w1-1][h2-1][w2]

* 用T表示这四种状态里面最优的一个

* T=max(f[h1-1][w1][h2-1][w2]，f[h1][w1-1][h2][w2-1]，f[h1-1][w1][h2][w2-1]，f[h1][w1-1][h2-1][w2])

* 如果(h1,w1)==(h2,w2)

* f[h1][w1][h2][w2]=a[h1][w1]+T

* 如果(h1,w1)!=(h2,w2)

* f[h1][w1][h2][w2]=a[h1][w1]+a[h2][w2]+T

 

四、AC代码

5ms

1 /*  2  * codeVs1043方格取数.cpp  3  * 分析：  4  * 把这个问题看成两个人同时走就ok了  5  * 状态：  6  * f[h1][w1][h2][w2]表示第一个人走到(h1,w1)位置和第二个人走到(h2,w2)位置所取的最大和  7  * 最终状态：  8  * f[n][n][n][n]  9  * 初始状态： 10  * f[0][0][0][0] （都没走的情况，这就是最初的情况） 11  * 只可能两个人同时走了或者没走，不可能一个人走了，一个人没走 12  * 13  * 状态转移方程： 14  * 走到(h1,w1)，(h2,w2)的四种方式： 15  * 1、都向下走 f[h1-1][w1][h2-1][w2] 16  * 2、都向右走 f[h1][w1-1][h2][w2-1] 17  * 3、第一个人向下，第二个人向右 f[h1-1][w1][h2][w2-1] 18  * 4、第一个人向右，第二个人向下 f[h1][w1-1][h2-1][w2] 19  * 用T表示这四种状态里面最优的一个 20  * T=max(f[h1-1][w1][h2-1][w2]，f[h1][w1-1][h2][w2-1]，f[h1-1][w1][h2][w2-1]，f[h1][w1-1][h2-1][w2]) 21  * 如果(h1,w1)==(h2,w2) 22  * f[h1][w1][h2][w2]=a[h1][w1]+T 23  * 如果(h1,w1)!=(h2,w2) 24  * f[h1][w1][h2][w2]=a[h1][w1]+a[h2][w2]+T 25  * 26  */ 27  28 #include 
     
       29 #include 
      
        30 #define maxn 13 31 using namespace std; 32 int n; 33 int f[maxn][maxn][maxn][maxn]; 34 int a[maxn][maxn]; 35  36 void initArr_a() { 37     for (int i = 1; i < maxn; i++) { 38         for (int j = 1; j < maxn; j++) { 39             a[i][j] = 0; 40         } 41     } 42 } 43  44 void readData() { 45     cin >> n; 46     int h, w, x; 47     while (scanf("%d %d %d", &h, &w, &x) == 3) { 48         bool t1 = h == 0 && w == 0 && x == 0; 49         if (t1) 50             break; 51         a[h][w] = x; 52     } 53 } 54  55 void printArr_a() { 56     for (int i = 1; i <= n; i++) { 57         for (int j = 1; j <= n; j++) { 58             printf("%5d", a[i][j]); 59         } 60         cout << endl; 61     } 62 } 63  64 void initArr_f() { 65     for (int i1 = 0; i1 <= n; i1++) { 66         for (int i2 = 0; i2 <= n; i2++) { 67             for (int i3 = 0; i3 <= n; i3++) { 68                 for (int i4 = 0; i4 <= n; i4++) { 69                     f[i1][i2][i3][i4] = 0; 70                 } 71             } 72         } 73     } 74     //都没出发的情况 75     f[0][0][0][0] = 0; 76  77 } 78 void init() { 79     initArr_a(); 80     readData(); 81     //printArr_a(); 82     initArr_f(); 83 } 84  85 int max4(int a, int b, int c, int d) { 86     int tmp1 = max(a, b); 87     int tmp2 = max(c, d); 88     return max(tmp1, tmp2); 89 } 90  91 void dp() { 92     for (int i1 = 1; i1 <= n; i1++) { 93         for (int i2 = 1; i2 <= n; i2++) { 94             for (int i3 = 1; i3 <= n; i3++) { 95                 for (int i4 = 1; i4 <= n; i4++) { 96                     int tmp= max4(f[i1-1][i2][i3-1][i4],f[i1][i2-1][i3][i4-1],f[i1-1][i2][i3][i4-1],f[i1][i2-1][i3-1][i4]); 97                     if(i1==i3&&i2==i4){ 98                         f[i1][i2][i3][i4]=a[i1][i2]+tmp; 99                     }100                     else{101                         f[i1][i2][i3][i4]=a[i1][i2]+a[i3][i4]+tmp;102                     }103                 }104             }105         }106     }107 }108 109 void printAns(){110     cout<
       
        <
       
      
     

 

 

 

五、注意点

1、在找初始状态上面还有点问题       一般是f[i][0],f[0][j],f[0][0]，还有一些看题目       多维也是仿照两维来写状态转移方程2、找准初始状态的实际意义，状态转移方程就好写了3、向下和向右走正好对应x，y的++