problem
luogu-P3648
你正在玩一个关于长度为的非负整数序列的游戏。在这个游戏中,您需要将序列分成个非空块。
要获得块,需要重复以下操作次:
- 选择一个包含多个元素的块(最初你只有一个块,即整个序列)
- 选择两个相邻的元素将中间的块分割,产生两个非空块。
- 每次操作后,您将获得这两个新生成的块的元素总和乘积的分数。
你想最大化最终的总分。
输出最终分数和任一除法方案。
solution
前提结论:分数与削减的顺序无关。
假设你想把切成。
- 先剪,再剪、。
- 先切,再切,。
这将从左到右。注,即元素分数前缀总和。
将前的数设置为段的最高分。
然后。
只和有关,考虑参考最外层循环,内层简写为。
假设,决策优于。
必须满足:
是前缀和数组,所以是单调的。
标准斜率优化公式,因为已经不能接受一个,所以我最喜欢的李超书被掉了。
斜率优化最麻烦的就是在头尾弹出时使用队列来维护符号大小的方向问题。
网上一堆凸包图对于我这种平面几何感几乎为零的魔芋来说简直是天方夜谭。
所以这里写一个判断方法,不保证正确性
- 组长的弹窗很简单,因为上面的坡度优化公式已经求解了,直接和和比较。
如果表明是后者,更好。
你需要一个班长。 - 考虑到和,队列末尾的弹出窗口更复杂。
准确地说,是考虑是否有可能成为团队的领导者。
那么当当前队尾在后面的某个枚举位置时,就成为队首,
必须满足,才能弹出。 - 假设炸弹尾部的条件是。
显然有的可能性。
所以这样玩可能会弹出答案的价值点。 - 假设炸弹尾部的条件是。
因为,
所以被弹出后,会立即被弹出。
那么 永远不能成为团队的领导者。
综上所述,我们确定了尾部判断的符号。
注意:前面的说法表明不是严格递增的,而且是有平台的,所以遇到时返回到斜率的最小值。
code
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define maxn 100005
int n, k, d;
int a[maxn], sum[maxn], q[maxn];
int g[maxn][205], f[maxn][205];
double slope( int x, int y ) {
if( sum[x] == sum[y] ) return -1e18;
return (f[x][d] - sum[x] * sum[x] - f[y][d] + sum[y] * sum[y]) * 1.0 / (sum[y] - sum[x]);
}
void print( int n, int d ) {
if( d == 1 ) return;
print( g[n][d], d - 1 );
printf( "%d ", g[n][d] );
}
signed main() {
scanf( "%lld %lld", &n, &k );
for( int i = 1;i <= n;i ++ ) scanf( "%lld", &a[i] );
for( int i = 1;i <= n;i ++ ) sum[i] = sum[i - 1] + a[i];
for( d = 1;d <= k;d ++ ) {
int head = 1, tail = 0;
for( int i = 1;i <= n;i ++ ) {
while( head < tail and slope( q[head], q[head + 1] ) <= sum[i] ) head ++;
f[i][d + 1] = f[q[head]][d] + sum[q[head]] * ( sum[i] - sum[q[head]] );
g[i][d + 1] = q[head];
while( head < tail and slope( q[tail - 1], q[tail] ) >= slope( q[tail], i ) ) tail --;
q[++ tail] = i;
}
}
printf( "%lld\n", f[n][d] );
print( n, d );
return 0;
}
文章出处登录后可见!
已经登录?立即刷新