#C241017D. [NOIP2000 提高组] 方格取数（加强版）

标签（Label）

动态规划
维度压缩

网址（Website）

方格取数「加强版」 - Super

题目（Problem）

题目描述

有一个 $n \times m$ 的矩阵，每个格子里有不同的正整数。

$\mathrm{Tom}$ 从图的左上角出发，可以向下行走，也可以向右走，直到到达右下角。

$\mathrm{Tom}$ 在走过的路上，他可以取走方格中的整数（取走后的方格中将变为数字 $0$）。

$\mathrm{Tom}$ 从左上角走到右下角共走两次，请你替 $\mathrm{Tom}$ 找出 $2$ 条这样的路径，使得取得的整数之和为最大。

输入格式

第一行为两个整数 $n$ 和 $m$，分别表示矩阵的行和列。

接下来有 $n$ 行，每行 $m$ 个整数。

输出格式

输出一个整数，即两条路径取得整数之和的最大值。

样例

输入数据 1

输出数据 1

样例1说明

第一条路径：
$(1,1) \rightarrow (2,1) \rightarrow (3,1) \rightarrow (3,2) \rightarrow (3,3)$，取得整数和：$1 + 5 + 5 + 5 + 1 = 17$，矩阵变成：

$\begin{matrix}
0 & 4 & 4 \
0 & 1 & 4 \
0 & 0 & 0
\end{matrix}$

第二条路径：
$(1,1) \rightarrow (1,2) \rightarrow (1,3) \rightarrow (2,3) \rightarrow (3,3)$，取得整数和：$0 + 4 + 4 + 4 + 0 = 12$，矩阵变成：

$\begin{matrix}
0 & 0 & 0 \
0 & 1 & 0 \
0 & 0 & 0
\end{matrix}$

两条路径取得整数之和为：$17 + 12 = 29$，且为最大值。

数据规模与约定

对于 $30%$ 的数据，$2 \leq n, m \leq 20$。

对于 $100%$ 的数据，$2 \leq n, m \leq 200$；$1 \leq$ 题目给出的整数 $\leq 1000$。

题解（Solution）

简单版在这里→ 方格取数 - WolfDeer

$\qquad$题解讲的最清楚的一次，这个应该是最板子的 $\mathrm{dp}$ 维度压缩，在已经有 $f[a][b][c][d]$ 的基础上，我们发现要压成 $n^3$ 的状态，既然要压状态，就需要找到相同点。我们观察到题目中两条路径最终的步数是一样的，便考虑枚举步数 $s$ ，发现此时只需要知道对应两条路径在哪两行就能知道当前两条路径在的点的位置，这道题便迎刃而解了。

出题者题解

算法分析

首先，用最基本的动态规划模拟走两遍不一定是最优的，可以自行构造反例，这题必须从双管齐下的角度入手。那么首先要想到一种方案来存储两条路线的状态，先想到的一般是 $f[i][j][k][l]$ 来表示路径 $1$ 走到点 $(i,j)$，路径 $2$ 走到点 $(k,l)$ 的状态。那想想怎么解决一个格子过两遍只能收益一次的问题。按照这个状态，没法知道在某个状态，一个点有没有被路径 $1$ 或者路径 $2$ 遍历过。

但可以知道，如果一个点被遍历了两遍，那么这个点是同时被两条路径遍历的。这建立在每次两条路径同时增加一步的条件上，因为可以想象，只要每次都只走一步，那每个时刻都满足 $i + j = k + l$。从这个角度看，一来限了状态的冗余，二来用 $i + j = k + l$ 可以解决上一段提到的“过两遍问题”。不需要思考“一条路径会不会经过另外一条路径已经走过的点的问题”，这个事件已经不会发生了，因为现在所有路径都是等长的，只要处理好两条路径走到同一个点的事件就能放心转移了。

顺便化简状态，记 $s = i + j = k + l$，相当于是走过的步数（加 $2$），用状态 $f[s][i][k]$ 表示走了 $s - 2$ 步以后路径 $1$ 在第 $i$ 行（第 $s - i$ 列），路径 $2$ 在第 $k$ 行（第 $s - k$ 列），就能不带冗余地表示出所有需要的状态了。

接下去的转移就很轻松了：$f[s][i][k]$ 这个状态的前继，是由四个前继转移过来的，每条路径都可以选择向下或者向右，即 $f[s-1][i][k]$，$f[s-1][i-1][k]$，$f[s-1][i][k-1]$ 和 $f[s-1][i-1][k-1]$。多出来的贡献是这个两个当前点数值和，如果是同一个点就只加一次。

代码（Code）

#include<bits/stdc++.h>
#include<vector>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define x first
#define y second
inline int rd(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f;
const int N = 505;
bool ST;

int a[N][N];
int n,m;
int f[N][N][N];

void solve(){
	n = rd(), m = rd();For(i,1,n) For(j,1,m) a[i][j] = rd();
	For(s,1,n+m){
		int l = max(s-m,1), r = min(n,s-1);
		For(i,l,r) For(j,l,r){
			f[s][i][j] = max({f[s-1][i][j], f[s-1][i-1][j], f[s-1][i][j-1], f[s-1][i-1][j-1]});
			if(i==j) f[s][i][j] += a[i][s-i];
			else f[s][i][j] += a[i][s-i] + a[j][s-j];
		}
	}printf("%d\n", f[n+m][n][n]);
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	int T = 1, Tim = clock();
	while(T--) solve();
	return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}