P7959 [COCI2014-2015#6] WTF 题解
呃，是一道
DP题
说实话，原题实际上是不要输出一种方法的……但是似乎放这道题的人想增加一点难度？
这里有两种做法，但都是 DP。
预备观察
我们首先观察一些性质，以方便解题。
-
循环不变：我们可以观察到，在 \(n\) 次变换后，序列会还原。也就是说，两个循环在同一个 \(i\) 上操作的序列是一样的。
-
下标大小：其实可以看到，下标是一大一小，也就是 \(\min(ID_{i}, \mathit{ID}_{i+1})\) 和 \(\max(ID_{i}, ID_{i + 1})+1\)。意味着我们在 \(ID_{i}\) 的选择关于，且仅关于 \(ID_{i - 1}\) 的选择。所以考虑
DP转移。 -
连续性：不难发现，其实选择是这么一些边：\((ID_{i}, ID_{i + 1})\) 和 \((ID_{i + 1}, ID_{i + 2})\)，也就是说每一个状态是相关联的。
接下来就可以开始正式解题了。
感觉上面讲的都是废话
解法1：强行DP
这也是我拿到这一道题的第一想法……也是正解的一种吧
在观察出来下标大小的关系之后，其实就可以设一个 \(DP\) 了。
令 \(f_{i,j}\) 表示在 \(ID_{i + 1}\) 选 \(j\) 所能取到的最大值。
于是可以有这么一个转移方程：
\[f_{i,j} = \max_{k=1}^{n-1}(f_{i-1,k} + A_{\min(j, k)} - A_{\max(j,k) + 1}) \]\(k\) 上界为 \(n - 1\)，这是题面中要求了的。
包括 \(j\) 其实也 \(\in [1, n-1]\)
所以就有一个 \(O(n^3)\) 的写法了。
但是很明显，必须优化到 \(O(n^2)\) 才能过。
我们把 \(\min \max\) 拆开：
\[\begin{aligned} f_{i,j} = \max&( A_{j} + \max_{k = j}^{n - 1}(f_{i-1, k} - A_{k+1}), \\ &-A_{j+1} + \max_{k = 1}^{j}(f_{i-1,k} + A_{k})) \end{aligned} \]其实内部关于 \(j\) 的边界并没有那么重要
很明显，后面两个部分可以通过前后缀 \(\max\) 搞定。于是我们可以在 \(O(1)\) 内转移。
总时间复杂度成功变为 \(O(n^2)\)。
不过还要注意一个点，每一次转移的时候，需要手动模拟一次 \(Rotate(n, r)\)。
那么核心代码如下：
pre[0] = suf[n] = -1e9;
for (i = 1; i <= n; ++i, rotate()) {
// prefix k
for (k = 1; k < n; ++k) {
// pre[k] = max(pre[k - 1], f[i - 1][k] + A[k]);
if (pre[k - 1] >= f[i - 1][k] + A[k]) {
pre[k] = pre[k - 1];
pref[k] = pref[k - 1];
} else {
pre[k] = f[i - 1][k] + A[k];
pref[k] = k;
}
}
// suffix k
for (k = n - 1; k; --k) {
// suf[k] = max(suf[k + 1], f[i - 1][k] - A[k + 1]);
if (suf[k + 1] >= f[i - 1][k] - A[k + 1]) {
suf[k] = suf[k + 1];
suff[k] = suff[k + 1];
} else {
suf[k] = f[i - 1][k] - A[k + 1];
suff[k] = k;
}
}
for (j = 1; j < n; ++j) { // enum cur ID[i + 1]
int p = pre[j] - A[j + 1], s = suf[j] + A[j];
if (p >= s) {
f[i][j] = p;
trans[i][j] = pref[j];
} else {
f[i][j] = s;
trans[i][j] = suff[j];
}
}
}
最后通过 trans 数组输出方案即可。
不过说实话，这个空间复杂度确实不够优秀。
做法2：std做法
其实可以发现，对于每一个 \(i\)，设
\[id_1 = \min(ID_{i}, ID_{i + 1}), id_2 = \min(ID_{i}, ID_{i + 1}) \]于是有 \(sum += A_{id_1} -A_{id_2 +1}\)。
这似乎提醒这我们做一个前缀差分。
于是我们设 \(b_{i} = A_{i + 1} - A_{i}\)。
所以可以得到 \(A_{id_2 + 1} - A_{id_1} = \sum_{i = id_1}^{id_2} b_{i}\)。
原本我们需要最大化，那么此时，我们需要最小化 \(A_{id_2 + 1} - A_{id_1}\)。
不过，如果我们把初始的 \(A\) 序列全部取反，那么我们还是需要最大化上面这个式子。
贴出的代码中也做了如上操作。
注意加减顺序。以及 \(b\) 只有 \(n-1\) 个元素。
于是我们可以构建出一个 \((n-1) \times n\) 的矩阵 \(B\)，其中每一行是对应旋转后的 \(A\) 的差分序列。
我们在寻找 \(sum\) 的过程，其实就是把所有路径上的 \(b\) 加起来，于是，问题转化为寻找在 \(B\) 上的一条最短路径。
不过，由于我们只能向下，或者左右走，并且不能重复走，所以也考虑 \(DP\)。
设 \(f_{i, j, k}\) 表示，走到 \((i, j)\) 这个位置，来的方向是 \(k\) ，的最长路径。
\(k \in [0, 3)\)，分别表示从上面转移，从右侧转移，从左侧转移。
或者可以说是向下走，向右走，向左走转移（代码中的意义）。
于是有如下方程：
\[\begin{aligned} f_{i, j, 0} &= \max(f_{i-1, j, 0/1/2}) + B_{i,j} \\ f_{i, j, 1} &= \max(f_{i, j+1, 0/1}) + B_{i, j} \\ f_{i, j, 2} &= \max(f_{i, j-1, 0/2}) + B_{i, j} \end{aligned} \]记录一下转移来的路径，在拐点的地方输出即可。
为了偷懒，就直接贴出不记录路径的代码了。
总时间复杂度 \(O(n^2)\)：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 3003, MINUS_INF = -1e9;
int a[N][N];
int b[N][N];
int dp[N][N][3];
#define DOWN 0
#define LEFT 1
#define RIGHT 2
// 三个方向选其优
int best(int i, int j) {
return max(dp[i][j][DOWN],
max(dp[i][j][LEFT], dp[i][j][RIGHT]));
}
int main () {
int n, r;
cin >> n >> r;
// 注意整个程序的下标是从 0 开始
// 也就是 [0, n) 而非 [1, n]
for (int i = 0; i < n; ++i) {
cin >> a[0][i];
a[0][i] *= -1;
int position = i;
// 构建旋转后的序列
for (int j = 1; j < n; ++j) {
position = (position + r) % n;
a[j][position] = a[0][i];
}
}
// 初始化dp表
for (int i = 0; i < n; ++i)
for (int j = 0; j < n - 1; ++j) {
// 构建差分序列
b[i][j] = a[i][j + 1] - a[i][j];
for (int k = 0; k < 3; ++k)
dp[i][j][k] = MINUS_INF;
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n - 1; ++j) {
// 处理从上一行的转移
dp[i][j][DOWN] = b[i][j] + (i > 0 ? best(i - 1, j) : 0);
// 处理从左边转移
if (j > 0)
dp[i][j][RIGHT] = b[i][j] +
max(dp[i][j - 1][DOWN], dp[i][j - 1][RIGHT]);
}
// 反着来一次从右边的转移
for (int j = n - 3; j >= 0; --j)
dp[i][j][LEFT] = b[i][j] +
max(dp[i][j + 1][DOWN], dp[i][j + 1][LEFT]);
}
// 输出最终的答案
int sol = MINUS_INF;
for (int j = 0; j < n - 1; ++j)
sol = max(sol, best(n - 1, j));
cout << sol << endl;
}