题目翻译
题目给我们两个长度为n的数组a和数组b，我们需要从1到n中挑选一些区间[L1, R1], [L2, R2]…满足这些区间没有相交，同时直接区间的贡献最大，定义每个区间[l, r]的贡献是std::abs(a[l] - b[r]) + std::abs(b[l] - a[r])。
思路
首先我们容易思考到一个O（n * k * k)的暴力dp，我们可以定义dp[i] [j]表示考虑了前i个数，线段总长度为j的最大贡献，转移时O（k）的向前枚举即可。但这样的时间复杂度无法接受，考虑是否能够优化这个dp，绝对值不是很好处理，我们可以先把绝对值拆开，实际上只有a[l] - b[r] + b[l] - a[r], b[r] - a[l] + b[l] - a[r], a[l] - b[r] + a[r] - b[l], b[r] - a[l] + a[r] - b[l]，这四种方式的转移，因为绝对值的性质，我们取其中最大的转移方式即可。
注意到此时我们暴力dp的状态转移方程从dp[i] [j] = dp[i - k] [j - k] + std::abs(a[i - k + 1] - b[i]) + std::abs(b[i - k + 1] - a[i])变成了没有绝对值的形式，我们把dp[i - k] [j - k] 与 a[i - k + 1] 和 b[i - k + 1]联立在一起，发现这个转移实际上是一个前缀最大值，我们可以使用前缀和进行优化dp。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| void solve(){
int n, k;
std::cin >> n >> k;
std::vector<ll> a(n + 1, 0);
std::vector<ll> b(n + 1, 0);
for(int i = 1; i <= n; i++)
std::cin >> a[i];
for(int i = 1; i <= n; i++)
std::cin >> b[i];
std::vector dp(n + 1, std::vector<ll>(k + 1, 0));
std::vector f(n + 1, std::vector<ll>(4, -1e18));
for(int i = 1; i <= n; i++){
for(int j = 1; j <= std::min(k, i); j++){
f[i - j][0] = std::max(f[i - j][0], dp[i - 1][j - 1] + a[i] + b[i]);
f[i - j][1] = std::max(f[i - j][1], dp[i - 1][j - 1] - a[i] - b[i]);
f[i - j][2] = std::max(f[i - j][2], dp[i - 1][j - 1] - a[i] + b[i]);
f[i - j][3] = std::max(f[i - j][3], dp[i - 1][j - 1] + a[i] - b[i]);
dp[i][j] = dp[i - 1][j];
dp[i][j] = std::max(dp[i][j], f[i - j][0] - a[i] - b[i]);
dp[i][j] = std::max(dp[i][j], f[i - j][1] + a[i] + b[i]);
dp[i][j] = std::max(dp[i][j], f[i - j][2] - a[i] + b[i]);
dp[i][j] = std::max(dp[i][j], f[i - j][3] + a[i] - b[i]);
}
}
std::cout << dp[n][k] << endl;
}
|
