65088 - [NOIP2008 提高组] 传纸条 message

解决方法

此题与数字三角形(Acwing.898)属于一种DP模型，但区别在于，这里是从A走到B，再从B走到A，相当于走两遍；这个过程可以理解为两个不同的点从起点出发，沿着互不相交的收益最大路径走到终点（题目中条件“每个同学只能帮一次”暗示状态点只能被经过一次）从起点同时出发，意味着相同时刻，两点的横纵坐标值和一定相等。

由此，可以用f(k,x1,x2)表示状态，k=x1+y1=x2+y2；当x1=x2的时候，两条路径相交（走到了同一个点,x1=x2,y1=y2）注意只能经过一次，因此这种情况只能加一个s(x1,y1)；根据两条路径走最后一步的方向组合，分为四种情况：

①第一条路径最后一步由(x1-1,y1)到(x1,y1)，第二条路径最后一步由(x2-1,y2)到(x2,y2)。

②第一条路径最后一步由(x1-1,y1)到(x1,y1)，第二条路径最后一步由(x2,y2-1)到(x2,y2)。

③第一条路径最后一步由(x1,y1-1)到(x1,y1)，第二条路径最后一步由(x2-1,y2)到(x2,y2)。

④第一条路径最后一步由(x1,y1-1)到(x1,y1)，第二条路径最后一步由(x2,y2-1)到(x2,y2)。

两点重合时t=s(x1,y1)，当不重合时t=s(x1,y1)+s(x2,y2) 状态转移方程f(k,x1,x2)=max{①+t,②+t,③+t,④+t}

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN=55;
//走两遍的数字三角形模型
int m,n,s[MAXN][MAXN],f[2*MAXN][MAXN][MAXN];
int main(){
    cin>>m>>n;
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            cin>>s[i][j];
    for(int k=2;k<=(m+n);k++)
        for(int i1=1;i1<=m;i1++)//注意,枚举的是x方向,范围是1~m
            for(int i2=1;i2<=m;i2++){
                int j1=k-i1,j2=k-i2;
                if(j1>=1&&j1<=n&&j2>=1&&j2<=n){
                    int &x=f[k][i1][i2];
                    int t=s[i1][j1];
                    if(i1!=i2)
                        t+=s[i2][j2];
                    x=max(x,f[k-1][i1-1][i2]+t);
                    x=max(x,f[k-1][i1-1][i2-1]+t);
                    x=max(x,f[k-1][i1][i2-1]+t);
                    x=max(x,f[k-1][i1][i2]+t);
                }
            }
    cout<<f[m+n][m][m]<<endl;
    return 0;
}