自动搬运

查看原文

来自洛谷，原作者为

	喵仔牛奶 黄昏再美终要黑夜。

搬运于2025-08-24 22:37:12，当前版本为作者最后更新于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;
}