P7959 [COCI2014-2015#6] WTF 题解

p7959,coci2014,wtf,题解 · 浏览次数 : 18

小编点评

```cpp #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;}.归纳总结以上内容,生成内容时需要带简单的排版

正文

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;
}

与P7959 [COCI2014-2015#6] WTF 题解相似的内容: