题解：P8239 [AGM 2022 资格赛] 分裂

喵仔牛奶 · 2024-10-18 14:50:10 · 题解

Solution

容易发现，一段内加入数答案不减，所以如果分成的 k 个段可以不覆盖原序列，答案不变。

将 mx_i^{b_i}-mn_i^{b_i} 看成在第 i 段里随便选两个数 x,y，贡献为 a_x^{b_i}-a_y^{b_i}。容易发现答案还是不变，因为要求最大化，而选最大最小值是最优策略。

于是问题就变成取出 k 个不交段，每段取两个数（可以相同），一个正贡献，一个负贡献。

设 f_{i,j,0/1/2} 是 [1,i] 选了 j 段，状态是 0/1/2 的最大答案。0 表示第 j 段已经结束，1 表示第 j 段选过正贡献，2 表示选过负贡献。

转移简单，复杂度 \mathcal{O}(n^2)。

Code

#include <bits/stdc++.h>
#define REP(i, l, r) for (int i = (l); i <= (r); ++ i)
#define DEP(i, r, l) for (int i = (r); i >= (l); -- i)
#define fi first
#define se second
#define pb emplace_back
#define mems(x, v) memset((x), (v), sizeof(x))
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(), (x).end()
using namespace std;
namespace Milkcat {
    typedef long long LL;
    typedef pair<LL, LL> pii;
    const int N = 5005;
    LL n, k, a[N], b[N], f[2][N][3];
    void chkmax(LL &x, LL y) { x = max(x, y); }
    LL qpow(LL x, LL y) { return (y == 1 ? x : (y == 2 ? x * x : x * x * x)); }
    int main() {
        cin >> n >> k;
        REP(i, 1, n) cin >> a[i];
        REP(i, 1, k) cin >> b[i];
        mems(f, 0x8f), f[0][0][0] = 0;
        REP(i, 1, n) REP(j, 0, k) {
            int p = i & 1, q = i & 1 ^ 1;
            REP(x, 0, 2) f[p][j][x] = f[q][j][x];
            if (j > 0) {
                chkmax(f[p][j][0], f[q][j - 1][0]);
                chkmax(f[p][j][0], f[q][j][1] - qpow(a[i], b[j]));
                chkmax(f[p][j][0], f[q][j][2] + qpow(a[i], b[j]));
                chkmax(f[p][j][1], f[q][j - 1][0] + qpow(a[i], b[j]));
                chkmax(f[p][j][2], f[q][j - 1][0] - qpow(a[i], b[j]));
            }
        }
        cout << f[n & 1][k][0] << '\n';
        return 0;
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T = 1;
    while (T --) Milkcat::main();
    return 0;
}