题解 P1006 【传纸条】
ouuan
2018-07-09 13:25:56
前4页题解都没有用滚动数组的..碰到我出的[大教室中传纸条](https://www.luogu.org/problemnew/show/T35377)全得炸。
思路其它题解说的很清楚了，就是看成同时从左上开始传两个纸条，用f(i,j,k)表示这一步的横纵坐标之和为i，第一张纸条纵坐标为j，第二张纸条纵坐标为k（因为路径不重合，所以j≠k，不妨令j<k）。可以看出每走一步纸条的横纵坐标之和都会加一，所以i其实就是传递的次数+2.
每个状态可以由以下4种情况转移而来：
1. 第一张纸条由上面，第二张纸条由上面
f(i,j,k)=max{f(i,j,k),f(i-1,j-1,k-1)+a[j][i-j]+a[k][i-k]}
2. 第一张纸条由上面，第二张纸条由左边
f(i,j,k)=max{f(i,j,k),f(i-1,j-1,k)+a[j][i-j]+a[k][i-k]}
3. 第一张纸条由左边，第二张纸条由上面
f(i,j,k)=max{f(i,j,k),f(i-1,j,k-1)+a[j][i-j]+a[k][i-k]}
4. 第一张纸条由左边，第二张纸条由左边
f(i,j,k)=max{f(i,j,k),f(i-1,j,k)+a[j][i-j]+a[k][i-k]}
可以看出，每种转移都是在一定情况下才能发生的（没有越界，而且纸条没有重合）。由于一开始数组中都是0，不进行越界判断也无妨，但是纸条重合的判断必须有，即只有k-1>j时才能由第3种情况转移.
### 然后重点来了
本题解和前4页题解（没往后面翻了orz）的不同之处在于，用了滚动数组。其实就是因为转移时只会由f(i-1,x,y)转移而来，在数组中省去了i这一维，节约了一些空间。需要注意的就是由于状态都是由更小的j和/或k转移而来，j和k都需要倒序枚举，防止状态在转移之前被修改。
代码如下：
```
#include <fstream>
#include <iostream>
#include <algorithm>
using namespace std;
/*
这一部分是用来方便地转换标准io和文件io，
只需在#include <iostream>前加上//就可以转换为文件io
*/
#ifndef _GLIBCXX_IOSTREAM //这个在iostream头文件中define了，这句话的意思就是如果没有#include <iostream>则执行下面的语句
ifstream cin("0.in");
ofstream cout("0.out");
#endif
int n,m,f[210][210],a[210][210];
int main()
{
int i,j,k;
cin>>n>>m;
for (i=1;i<=n;++i)
{
for (j=1;j<=m;++j)
{
cin>>a[i][j];
}
}
f[1][2]=a[1][2]+a[2][1];
for (i=4;i<n+m;++i)
{
for (j=min(i-2,n);j>=1;--j) //注意要倒序枚举j和k
{
for (k=min(i-1,n);k>j;--k)
{
if (j>1) //这里的条件判断貌似是不需要的，但我觉得加上更好
{
f[j][k]=max(f[j][k],f[j-1][k]);
}
if (j>1&&k>1)
{
f[j][k]=max(f[j][k],f[j-1][k-1]);
}
if (k-1>j)
{
f[j][k]=max(f[j][k],f[j][k-1]);
}
f[j][k]+=a[j][i-j]+a[k][i-k];
}
}
}
cout<<f[n-1][n];
return 0;
}
```