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

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

数据范围及提示 Data Size & Hint

如描述

分类标签 Tags 点此展开

动态规划棋盘型DP 深度优先搜索搜索大陆地区 NOIP全国联赛提高组 2000年

三、分析

* 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 <iostream>
 29 #include <cstdio>
 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<<f[n][n][n][n]<<endl;
111 }
112 
113 int main() {
114     //freopen("src/codeVs1043.txt", "r", stdin);
115     init();
116     dp();
117     printAns();
118     return 0;
119 }
120 
121 /*
122  * 注意点
123  * 1、在找初始状态上面还有点问题
124  *         一般是f[i][0],f[0][j],f[0][0]，还有一些看题目
125  *         多维也是仿照两维来写状态转移方程
126  * 2、找准初始状态的实际意义，状态转移方程就好写了
127  * 3、向下和向右走正好对应x，y的++
128  */

五、注意点

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