三维dp,搜索方式注意下。

#include<bits/stdc++.h>
using namespace std;

const int inf = 0x3f3f3f3f;

int dp[110][110][3];
int mat[110][110];

int main ()
{
    int t;
    int icase = 1;
    scanf("%d", &t);
    while (t--){
        int n, m;
        scanf("%d%d", &n, &m);
        memset (dp, -inf, sizeof(dp));
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 1; j <= m; ++j)
            {
                scanf("%d", &mat[i][j]);
            }
        }
        dp[1][1][0] = dp[1][1][1] = dp[1][1][2] = mat[1][1];
        for (int i = 2; i <= n; ++i)
        {
            dp[i][1][0] = dp[i - 1][1][0] + mat[i][1];
        }
        for (int j = 2; j <= m; ++j)
        {
            for (int i = 1; i <= n; ++i) //从左边进入
            {
                dp[i][j][2] = max (dp[i][j - 1][0], max (dp[i][j - 1][1], dp[i][j - 1][2])) + mat[i][j];
            }
            for (int i = 2; i <= n; ++i)
            {
                dp[i][j][0] = max (dp[i - 1][j][0], dp[i - 1][j][2]) + mat[i][j];
            }
            for (int i = n - 1; i >= 1; --i)
            {
                dp[i][j][1] = max (dp[i + 1][j][2], dp[i + 1][j][1]) + mat[i][j];
            }
        }
        int ans = max (dp[1][m][0], max (dp[1][m][1], dp[1][m][2]));
        printf("Case #%d:\n", icase++);
        printf ("%d\n", ans);
    }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注