给定一个$2*n$的矩阵，从中选出若干数，且任意两个数不上下或左右相邻，求这些数的最大总和
$1\le n \le 100000,1 \le h_{i,j}\le 1000000000$
很水的一道C题……目测难度在黄~绿左右。请各位切题者合理评分。
注意到可以选择的球员编号是严格递增的，因此可以把状态的第一维定义为球员编号，第二维描述编号同为 $i$ 的两名球员的选取情况。
定义状态：$f[i][0/1/2]$ 表示选取了编号在 $i$ 及以前的球员，所能得到的身高总和最大值。其中，第二维的 $0$ 表示编号为 $i$ 的球员一个都不选；$1$ 表示只选上面一个；$i$ 表示只选下面一个。（显然没有上下都选的情况）
状态转移方程：
$$
f[i][0]=max\lbrace f[i-1][0],f[i-1][1],f[i-1][2]\rbrace
$$
$$
f[i][1]=max\lbrace f[i-1][0],f[i-1][2]\rbrace+height[i][1]
$$
$$
f[i][2]=max\lbrace f[i-1][0],f[i-1][1]\rbrace+height[i][2]
$$
Update: 用贪心可以证明，在最优解中，不会出现连续两列一个不取的情况。因此， $f[i][0]$ 其实没有必要考虑来自 $f[i-1][0]$ 的状态转移。
代码如下：
1 | #include <bits/stdc++.h> |