[NOIP2008] 传纸条 题解

题目描述：

题解：

首先转换一下问题，原问题就等价于从找两条从$(1,1)$到$(n,m)$的互不相交的路径，使得路径上数值的和最大。

首先考虑令$f[i,j,k,l]$表示两条路径到$(i,j)$于$(k,l)$时的最大夹着，这时候我们发现，如果知道了“走”了多少步，那么只要知道横坐标（或纵坐标），就能根据走的步数算出令一个坐标，一举两等，大大简化状态转移。

于是我们令$f[k,i,j]$表示当走了k步，第一张纸条到第i行，第二张纸条到第j行时的最大价值。

于是状态转移方程为：

　　$f[k,i,j]=max{f[k-1][i][j](两个都向右走),f[k-1][i][j-1],f[k-1][i-1][j](一个向右一个向下),f[i-1][i-1][j-1](都向下走)}$

 注意循环对i,j的时候，j从i+1开始（为了保证路径不重合，也可以做到不重不漏）。

附上代码：

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

int a[60][60],f[101][60][60];
int n,m;


int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            scanf("%d",&a[i][j]);
    for(int k=2;k<=n+m-1;++k){
        for(int i=1;i<=n;++i){
            for(int j=i+1;j<=n;++j){
                if(!(k-i+1) || !(k-j+1) ||(k-i+1>m+1) || (k-j+1)>m+1) continue;//有效位置
                f[k][i][j]=max(f[k-1][i-1][j-1],f[k-1][i][j]);
                f[k][i][j]=max(f[k][i][j],max(f[k-1][i][j-1],f[k-1][i-1][j]))+a[i][k-i+1]+a[j][k-j+1];
            }
        }
    }
    printf("%d",f[n+m-1][n-1][n]);
    return 0;
}