洛谷P1006 传纸条 （棋盘dp）

好气，在洛谷上交就过了，在caioj上交就只有40分

之前在51nod做过这道题了。

https://blog.****.net/qq_34416123/article/details/81809024

#include<cstdio>
#include<cstring>
#include<algorithm>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;

const int MAXN = 55;
int map[MAXN][MAXN], f[MAXN<<1][MAXN][MAXN], m, n;

void up(int& x, int a) { x = max(x, a); }

int main()
{
    scanf("%d%d", &n, &m);
    REP(i, 1, n + 1)
        REP(j, 1, m + 1)
            scanf("%d", &map[i][j]);

    f[2][1][1] = map[1][1];
    REP(k, 2, n + m + 1)
        for(int x1 = 1; x1 <= n && x1 + 1 <= k; x1++)
            for(int x2 = 1; x2 <= n && x2 + 1 <= k; x2++)
            {
                int y1 = k - x1, y2 = k - x2;
                up(f[k][x1][x2], f[k-1][x1-1][x2]);
                up(f[k][x1][x2], f[k-1][x1][x2]);
                up(f[k][x1][x2], f[k-1][x1][x2-1]);
                up(f[k][x1][x2], f[k-1][x1-1][x2-1]);

                f[k][x1][x2] += map[x1][y1];
                if(x1 != x2) f[k][x1][x2] += map[x2][y2];
            }
        printf("%d\n", f[n+m][n][n]);

    return 0;
}