方格取数（DP）

Problem H: 方格取数

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 28  Solved: 9

Description

有N * N个格子，每个格子里有正数或者0，从最左上角往最右下角走，只能向下和向右，一共走两次（即从左上角走到右下角走两趟），把所有经过的格子的数加起来，求最大值SUM，且两次如果经过同一个格子，则最后总和SUM中该格子的计数只加一次。

 

Input

第一行N（1 <= N <= 100）

然后N行,每行N个数。依次表示N * N每个格子的数值。（0 <= value <= 1000） ;

 

Output

输出最大值SUM。

 

Sample Input

3

1 2 3

0 2 1

1 4 2

Sample Output

15

HINT

 

Hint

Possible Way：

第一次 1 -> 2 -> 2 -> 4 -> 2

第二次 1 -> 2 -> 3 -> 1 -> 2 

SUM = 15

 

 

       思路：

       DP。一共走两次，可以看成两个人同时从起点走向终点。每个点都可以从上面或者左边得到，所以两个人同时走的话，可以有四种组合。故可以得到转移方程：

       Dp [ X1 ] [ Y1 ] [ X2 ] [ Y2 ] = max （Dp [ X1 - 1 ] [ Y1 ] [ X2 - 1 ] [ Y2 ] , 

                                                               Dp [ X1 - 1 ] [ Y1 ] [ X2 ] [ Y2 - 1 ] ,

                                                               Dp [ X1 ] [ Y1 - 1 ] [ X2 - 1 ] [ Y2 ] ,

                                                               Dp [ X1 ] [ Y1 - 1 ] [ X2 ] [ Y2 - 1 ] ）+ Map [ X1 ] [ Y1 ] + Map [ X2 ] [ Y2 ]；

       四个循环，范围为 1 ~ 100，那么时间复杂度 O（n ^ 4）会造成 TLE，所以还要进一步优化。用 k 代表步数，那么转移方程可以变为：

       Dp [ k ] [ X1 ] [ X2 ]  = max （Dp [ k - 1 ] [ X1 - 1 ] [ X2 - 1 ]  , 

                                                    Dp [ k - 1 ] [ X1 - 1 ] [ X2 ]  ,

                                                    Dp [ k - 1 ] [ X1 ] [ X2 - 1 ] ,

                                                    Dp [ k - 1 ] [ X1 ] [ X2 ] ） + Map [ X1 ] [ k - X1 ] + Map [ X2 ] [ k - X2 ]；

       这样的话时间复杂度降为 O （n ^ 3 ）就不会导致TLE了。

 

       如何避免走相同的格的时候只加一次呢？

       因为 k 是一样的，说明当 x1 == x2 的时候，y1 == y2，这时候两个走在了同一格，所以只要判断是否 x1 == x2 就能决定要不要加两次了。若题目要求改为不允许走过同一点，将 x1 == x2 时候 continue 就可以了。

 

        AC：

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int dp[210][105][105];
int Map[105][105];

int main () {
            int n, sum;
            scanf("%d", &n);
            for (int i = 0; i < n; ++i)
                    for (int j = 0; j < n; ++j)
                            scanf("%d", &Map[i][j]);

            sum = n + n - 2;

            for (int k = 0; k <= sum; ++k) {
                for (int x1 = 0; x1 < n; ++x1) {
                    for (int x2 = 0; x2 < n; ++x2) {

                            int ans = 0;
                            int y1 = k - x1, y2 = k - x2;
                            if (k > 0 && x1 > 0 && x2 > 0)
                                ans = max(ans, dp[k - 1][x1 - 1][x2 - 1]);
                            if (k > 0 && x1 > 0 && y2 > 0)
                                ans = max(ans, dp[k - 1][x1 - 1][x2]);
                            if (k > 0 && y1 > 0 && x2 > 0)
                                ans = max(ans, dp[k - 1][x1][x2 - 1]);
                            if (k > 0 && y1 > 0 && y2 > 0)
                                ans = max(ans, dp[k - 1][x1][x2]);
                            if (y1 < 0 || y2 < 0) continue;

                            dp[k][x1][x2] = ans + Map[x1][y1] +
                                            (x1 == x2 ? 0 : Map[x2][y2]);

                    }
                }
            }

            printf("%d\n", dp[sum][n - 1][n - 1]);
        return 0;
}