Labyrinth

度度熊是一只喜欢探险的熊，一次偶然落进了一个m*n矩阵的迷宫，该迷宫只能从矩阵左上角第一个方格开始走，只有走到右上角的第一个格子才算走出迷宫，每一次只能走一格，且只能向上向下向右走以前没有走过的格子，每一个格子中都有一些金币（或正或负，有可能遇到强盗拦路抢劫，度度熊身上金币可以为负，需要给强盗写欠条），度度熊刚开始时身上金币数为0，问度度熊走出迷宫时候身上最多有多少金币？

输入的第一行是一个整数T（T < 200），表示共有T组数据。
每组数据的第一行输入两个正整数m，n（m<=100，n<=100）。接下来的m行，每行n个整数，分别代表相应格子中能得到金币的数量，每个整数都大于等于-100且小于等于100。

对于每组数据，首先需要输出单独一行”Case #?:”，其中问号处应填入当前的数据组数，组数从1开始计算。
每组测试数据输出一行，输出一个整数，代表根据最优的打法，你走到右上角时可以获得的最大金币数目。

2
3 4
1 -1 1 0
2 -2 4 2
3 5 1 -90
2 2
1 1
1 1

Case #1:
18
Case #2:
4

题目找不到了，还是保存一下。

初看以为是BFS，后来小兰说他用了BFS做TLE了，然后我在看题目发现用BFS我倒不会怎么写了，于是看着这题发呆了半天，还是不会。。。

但是后面搞到了小兰和yiyi学长做这题的思路，明白了怎么做的，结果很忧伤的是，找bug调试了一个下午。

此题要用DP，但该如何DP是好？

首先仅考虑对单个格子：对某个格子来说，它可以继承来自正上方，左方，正下方的格子过来的值，当然很自然的想到要取三者中的较大值。但是这样又有了一个问题：上方和下方的格子同样也有三个来源，其中包括了当前格子，但当前格子又要考虑上下左，于是陷入死循环。。

所以要换个方向。注意度度熊只能往右不能往左，这说明当度度熊一旦向右走就不能再回退。于是可以再推出，每当度度熊决定往右走的时候，一定是在当前列走了最优路径，且这个最优解的值并不受到它下一步的影响，所以每一次都取到最优解即可。

对于某个格子X[i][j]来说，度度熊过来的路可能是（上行或下行后，向右走）：

1. X[1][j-1] → X[i][j-1] → X[i][j];

2. X[2][j-1] → X[i][j-1] → X[i][j];

... ...

i-1. X[i-1][j-1] → X[i][j-1] → X[i][j];

i. X[i][j-1] → X[i][j];

i+1. X[i+1][j-1] → X[i][j-1] → X[i][j];

... ...

m. X[m][j-1] → X[i][j-1] →
X[i][j].

于是只用看每次过来的哪个是最优解就行了。但是要先预处理一下，算一下对每个格子求它到同列的第一行元素的sum，这样计算同列第i~k的元素之间的总和比较方便。

AC代码：

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#define MIN INT_MIN

using namespace std;

int T, t;
int m, n; //m行，n列
int map[101][101];
int dp[101][101];
int sum[101][101]; //每列和
int i, j;

//从下面上来
int down(int k)
{
        int tmp = MIN;
        while (k--)
        {
                tmp = max(tmp, sum[i+k+1][j]-sum[i][j]+dp[i+k+1][j-1]);
//                printf("down: i j tmp sum[%d][%d]-sum[%d][%d] dp[%d][%d] : %3d %3d %3d %3d %3d\n", i+k+1, j, i, j, i+k+1, j-1, i, j, tmp, sum[i+k+1][j]-sum[i][j], dp[i+k+1][j-1]);
        }
        return tmp;
}

//从上面下来
int up(int k)
{
        int tmp = MIN;
        while (k--)
        {
                tmp = max(tmp, sum[i-1][j]-sum[i-k-2][j]+dp[i-k-1][j-1]);
//                printf("up  : i j tmp sum[%d][%d]-sum[%d][%d] dp[%d][%d] : %3d %3d %3d %3d %3d\n", i-1, j, i-k-2, j, i-k-1, j-1, i, j, tmp, sum[i-1][j]-sum[i-k-2][j], dp[i-k-1][j-1]);
        }
        return tmp;
}

int main()
{
        #ifdef BellWind
                freopen("b_D.in", "r", stdin);
//                freopen("b_D.txt", "w", stdout);
        #endif // BellWind

        scanf("%d", &T);

        for (t = 1; t <= T; t++)
        {
                scanf("%d%d", &m, &n);
                memset(map, 0, sizeof(map));
                memset(sum, 0, sizeof(sum));
                memset(dp, 0, sizeof(sum));

                for (i = 1; i <= m; i++) {for (j = 1; j <=n; j++) {scanf("%d", &map[i][j]);}}

                for (j = 1; j <= n; j++)
                {
                        sum[1][j] = map[1][j];
                        for (i = 2; i <= m; i++)
                        {
                                sum[i][j] = sum[i-1][j] + map[i][j];
                        }
                }

//                //调试
//                printf("\nmap\n---------------\n");
//                for (i = 1; i <= m; i++)
//                {
//                        for (j = 1; j <= n; j++)
//                                printf("%4d ", map[i][j]);
//                        printf("\n");
//                }
//                printf("---------------\n\n");
//                //调试
//                printf("sum\n---------------\n");
//                for (i = 1; i <= m; i++)
//                {
//                        for (j = 1; j <= n; j++)
//                                printf("%4d ", sum[i][j]);
//                        printf("\n");
//                }
//                printf("---------------\n\n");

                for (i = 1; i <= m; i++) {dp[i][1] = sum[i][1];}

                for (j = 2; j <= n; j++)
                {
                        for (i = 1; i <= m; i++)
                        {
                                if (i == 1)
                                {
                                        int tmp = down(m-1);
                                        tmp = max(tmp, dp[i][j-1]);
                                        dp[i][j] = tmp + map[i][j];
//                                        printf("dp[%d][%d] map %3d %3d\n\n", i, j, dp[i][j], map[i][j]);
                                }
                                else if(i == m)
                                {
                                        int tmp = up(m-1);
                                        tmp = max(tmp, dp[i][j-1]);
                                        dp[i][j] = tmp + map[i][j];
//                                        printf("dp[%d][%d] map %3d %3d\n\n", i, j, dp[i][j], map[i][j]);
                                }
                                else
                                {
                                        int tmp1 = up(i-1);
                                        int tmp2 = down(m-i);
                                        int tmp = max(max(tmp1, tmp2), dp[i][j-1]);
                                        dp[i][j] += tmp + map[i][j];
//                                        printf("dp[%d][%d] map %3d %3d\n\n", i, j, dp[i][j], map[i][j]);
                                }
                        }
                }

//                //调试
//                printf("dp\n---------------\n");
//                for (i = 1; i <= m; i++)
//                {
//                        for (j = 1; j <= n; j++)
//                                printf("%4d ", dp[i][j]);
//                        printf("\n");
//                }
//                printf("---------------\n\n");

                printf("Case #%d:\n%d\n", t, dp[1][n]);
        }

        return 0;
}

话说这个代码为何调试如此多，是因为之前有个大bug一直没发现，就是算下行和算上行用了同样的方法，结果下行想算i~k的值就变成i+1~k+1的值了。。