传纸条

NOIP 题解

---

【问题描述】
小渊和小轩是好朋友也是同班同学，他们在一起总有谈不完的话题。一次素质拓展活动中，班上同学安排做成一个m行n列的矩阵，而小渊和小轩被安排在矩阵对角线的两端，因此，他们就无法直接交谈了。幸运的是，他们可以通过传纸条来进行交流。纸条要经由许多同学传到对方手里，小渊坐在矩阵的左上角，坐标(1,1)，小轩坐在矩阵的右下角，坐标(m,n)。从小渊传到小轩的纸条只可以向下或者向右传递，从小轩传给小渊的纸条只可以向上或者向左传递。

在活动进行中，小渊希望给小轩传递一张纸条，同时希望小轩给他回复。班里每个同学都可以帮他们传递，但只会帮他们一次，也就是说如果此人在小渊递给小轩纸条的时候帮忙，那么在小轩递给小渊的时候就不会再帮忙。反之亦然。

还有一件事情需要注意，全班每个同学愿意帮忙的好感度有高有低（注意：小渊和小轩的好心程度没有定义，输入时用0表示），可以用一个0-100的自然数来表示，数越大表示越好心。小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条，即找到来回两条传递路径，使得这两条路径上同学的好心程度只和最大。现在，请你帮助小渊和小轩找到这样的两条路径。

【输入】
输入文件message.in的第一行有2个用空格隔开的整数m和n，表示班里有m行n列（1<=m,n<=50）。
接下来的m行是一个m*n的矩阵，矩阵中第i行j列的整数表示坐在第i行j列的学生的好心程度。每行的n个整数之间用空格隔开。

【输出】
输出文件message.out共一行，包含一个整数，表示来回两条路上参与传递纸条的学生的好心程度之和的最大值。

【输入输出样例】
message.in
3 3
0 3 9
2 8 5
5 7 0

message.out
34

【限制】
30%的数据满足：1<=m,n<=10
100%的数据满足：1<=m,n<=50

【分析】
第一眼看到这个题感觉跟数字三角形很相像，觉得只要第一次找到最大路径后，把最大路径设为假，再找一次最大路径，他们两个的和就是最后结果，但结果就是:

Wrong Answer！

分两次找不行的话，那就合二为一，一次找出来回好心程度的最大值。

这样我们需要一个四维数组$f[i][j][k][l]$来表示传过来传到$（i,j）$，传回去传到$（k,l）$时最大的好心程度。

虽说题目中传过来只能往右或下走，传回去只能往上或左走，但是为了简化问题，我们完全可以把他看成两次都往右或下走，这完全是相同的。

题目中说到第一次帮助传纸条的人第二次就不会再帮忙，关于这个的处理也很简单，当$i=k$或$j=l$的时候直接进行下一次循环就可以了。

每走到一个位置，我们都要比较一下

$f[i][j-1][k][l-1]$ 第一二次都从左边

$f[i][j-1][k-1][l]$第一次从左边，第二次从上边

$f[i-1][j][k-1][l]$第一二次都从上面

$f[i-1][j][k][l-1]$第一次从上边，第二次从左边

中哪一个大？

我们可以得到状态转移方程式：

$f[i][j][k][l]=rect[i][j]+rect[k][l]+max \begin{cases} f[i-1][j][k-1][l], \\ f[i][j-1][k][l-1], \\ f[i-1][j][k][l-1],\\ f[i][j-1][k-1][l]\\ \end{cases}$

要注意的是如何输出最后的结果，由于我们上面判断$i=k$或$j=l$时，就进行下一次循环，这样$f[m][n][m][n]$是不会保存最后的结果的，$f[m][n][m][n]$只可能由$f[m-1][n][m][n-1]$或$f[m][n-1][m-1][n]$（终点的左边或上边）得到，所以我们只要比较一下$f[m-1][n][m][n-1]$和$f[m][n-1][m-1][n]$哪一个大就能得出最后的结果。

【AC程序】

#include<iostream>
using namespace std;
int rect[52][52]={0};
int f[52][52][52][52]={0};
int m,n;
int max(int a,int b){
    return ((a>b)?a:b);
}
int main(){
    cin>>m>>n;
    for (int i=1;i<=m;i++){
        for (int j=1;j<=n;j++){
            cin>>rect[i][j];
        }
    }
    for (int i=1;i<=m;i++){
        for (int j=1;j<=n;j++){
            for (int k=1;k<=m;k++){
                for (int l=1;l<=n;l++){
                    if (i==k||j==l) continue;
                    f[i][j][k][l]=rect[i][j]+rect[k][l]+max(max(f[i-1][j][k-1][l],f[i][j-1][k][l-1]),max(f[i-1][j][k][l-1],f[i][j-1][k-1][l]));
                }
            }
        }
    }
    cout<<max(f[m][n-1][m-1][n],f[m-1][n][m][n-1]);
    /*cout<<f[m][n][m][n];  f[m][n][m][n]中是不会储存最后结果的*/
    return 0;
}

【优化】
我们很容易知道，两次传递走的路程是相同的，我们可以得到一个等式 $i+j=k+l$
变形可得 $l=i+j-k$ 。
这样我们可以省掉一重循环，把时间复杂度从$O(n^4)$降到$O(n^3)$.
当然空间也可以压缩，但是我没写~

【优化后程序】

#include<iostream>
using namespace std;
int rect[52][52]={0};
int f[52][52][52][52]={0};
int m,n;
int max(int a,int b){
    return ((a>b)?a:b);
}
int main(){
    cin>>m>>n;
    for (int i=1;i<=m;i++){
        for (int j=1;j<=n;j++){
            cin>>rect[i][j];
        }
    }
    for (int i=1;i<=m;i++){
        for (int j=1;j<=n;j++){
            for (int k=1;k<=m;k++){
                int l=i+j-k;
                if (l<=0) continue;
                if (i==k||j==l) continue;
                f[i][j][k][l]=rect[i][j]+rect[k][l]+max(max(f[i-1][j][k-1][l],f[i][j-1][k][l-1]),max(f[i-1][j][k][l-1],f[i][j-1][k-1][l]));
            }
        }
    }
    cout<<max(f[m][n-1][m-1][n],f[m-1][n][m][n-1]);
    return 0;
}

End.