tyvj1011 - 传纸条 ——DP

题目链接：https://www.tyvj.cn/Problem_Show.aspx?id=1011 状态转移方程： f[k,x1,x2] = max(f[k-1,x1,x2],f[k-1,x1-1,x2],f[k-1,x1-1,x2-1],f[k-1,x1,x2-1]) + a[y1,x1] + a[y2,x2]; f[k,x1,x2]表示，第K步的时候，一条路的横坐标是x1,另一条路的横坐标是x2的时候所得到的最优解。另外，还要考虑一下，当x1==x2的时候的情况，这个时候，只能允许一条路走到那个位置。

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
using namespace std;
int a[51][51],f[100][51][51];
int main(void) {
    freopen("in1.txt","r",stdin);
    int N,M; scanf("%d%d", &M, &N);for(int i=1;i<=M;++i)for(int j=1;j<=N;++j)scanf("%d",&a[i][j]);
    for(int k=1;k<=M+N-3;++k)for(int x1=1;x1<=min(N,k+1);++x1)for(int x2=1;x2<=min(N,k+1);++x2) {
        f[k][x1][x2]=max(max(f[k-1][x1][x2],f[k-1][x1-1][x2]),max(f[k-1][x1][x2-1],f[k-1][x1-1][x2-1]));
        if (x1==x2)f[k][x1][x2]+=a[k-x1+2][x1]; else f[k][x1][x2]+=(a[k-x1+2][x1]+a[k-x2+2][x2]);
    } printf("%d\n",f[M+N-3][N][N-1]);
    return 0;
}

昨天看了一篇文章，才发现，其实，题解是写给自己看的-_-#