题解 P7074 【方格取数（民间数据）】
WanderingTrader
2020-11-15 22:38:50
好不容易有了一次给CSP写题解的机会，当然不能放过了。（滑稽）
比赛的时候先写了个 $O(n^2m)$ 的朴素dp，然后用10min优化到了 $O(nm).$
### 题目分析
我们先把状态定义出来：
令 $f(i,j)$ 为截止到第 $(i,j)$ 格时取到的整数之和最大值。
然而，小熊既可以往上走又可以往下走。如果直接按照状态转移的顺序进行连边，最终所得的图将不是一个DAG，直接求最长路会TLE或者WA.
突破口在于：虽然在上下方向可以随意走，但在左右方向只能向右。最终走到终点的时候，上下方向可能已经走了许多次，但左右方向一定只走了 $m-1$ 次。
于是我们把状态稍作修改：
令 $f(i,j)$ 为截止到第 $(i,j)$ 格，**而且走到此格后立刻向右走一步** 时取到的整数之和最大值。
那么转移路径就会由本来的这样：
变成这样（为了画面整洁只画出部分）：
很显然，这是一个DAG，可以直接做。
那么状态转移方程即为：
$f(i,j)=\max\{f(k,j-1)+s(i,k,j)|k\in[1,n]\}$
其中 $s(i,j,k)=\begin{cases}\sum\limits_{x=i}^{j-i+1}a(x,k)&(i<j)\\a(i,k)&(i=j)\\\sum\limits_{x=j}^{i-j+1}a(x,k)&(i>j)\end{cases}$，也就是第 $k$ 列上从 $i$ 到 $j$ 的连续和。
那么如果用前缀和优化，这个方程直接算用 $O(n^2m)$ 就可以了。
```cpp
void NsquareM()
{
for(int j=2;j<=m;++j)
{
for(int i=1;i<=n;++i)
{
f[i][j]=-inf;
for(int k=1;k<=i;++k)
f[i][j]=max(f[i][j],f[k][j-1]+s[i][j]-s[k-1][j]);
for(int k=i+1;k<=n;++k)
f[i][j]=max(f[i][j],f[k][j-1]+s[k][j]-s[i-1][j]);
}
}
printf("%lld\n",f[n][m]);
}
```
注意计算之前别忘了先设定成 $-\inf.$
那么如何优化呢？我们从代码入手：
```cpp
f[k][j-1]+s[i][j]-s[k-1][j]
f[k][j-1]+s[k][j]-s[i-1][j]
```
我们发现代码中一个很重要的特点：$i$ 和 $k$ 从不同时出现。那么我们可以分别把含 $i$ 的式子和含 $k$ 的式子整理出来：
```
f[k][j-1]+s[i][j]-s[k-1][j]
--- s[i][j] + (f[k][j-1]-s[k-1][j])
f[k][j-1]+s[k][j]-s[i-1][j]
--- -s[i-1][j] + (f[k][j-1]+s[k][j])
```
那么当 $j$ 确定时，括号里式子的最大值应该是定值，不随 $i$ 的变化而变化，因此可以预处理。
```cpp
void NM()
{
rMAX[n+1]=-inf;
for(int j=2;j<=m;++j)
{
LL MAX=-inf;
for(int i=n;i;--i) rMAX[i]=max(rMAX[i+1],f[i][j-1]+s[i][j]);
for(int i=1;i<=n;++i)
{
f[i][j]=-inf;
MAX=max(MAX,f[i][j-1]-s[i-1][j]);
f[i][j]=max(MAX+s[i][j],rMAX[i+1]-s[i-1][j]);
}
}
printf("%lld\n",f[n][m]);
}
```
（话说直接用时间复杂度做函数名的应该就我一个了吧）
这里MAX由于是顺推，所以直接一个变量
而 rMAX由于是逆推需要数组。
两重循环内部就这么变成了 $O(1)$ 。
比赛时担心优化写挂，于是主函数这样写了（freopen已注释）：
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=1e3+5;
const LL inf=1e12;
int n,m;
LL a[maxn][maxn],f[maxn][maxn],s[maxn][maxn],rMAX[maxn];
int main()
{
//freopen("number.in","r",stdin);
//freopen("number.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) for(int j=1;j<=m;++j)
{
scanf("%lld",&a[i][j]);
s[i][j]=s[i-1][j]+a[i][j];
}
for(int i=1;i<=n;++i) f[i][1]=s[i][1];
if(n*n*m<=1e7) NsquareM();
else NM();
return 0;
}
```
根据数据大小用不同的算法，这也是比赛时的一个小技巧。万一正解写挂了还能拿一点暴力分。
另外注意由于数据最多有 $10^6\times10^4=10^{10}$，需开long long。
此题最大的难点其实是写出转移方程，相较而言优化反而没有那么难了。
$$\texttt{The End.}$$