题目描述
你正在玩一个关于长度为 (n) 的非负整数序列的游戏。这个游戏中你需要把序列分成 (k + 1) 个非空的块。为了得到 (k + 1) 块，你需要重复下面的操作 (k) 次：
选择一个有超过一个元素的块（初始时你只有一块，即整个序列）
选择两个相邻元素把这个块从中间分开，得到两个非空的块。
每次操作后你将获得那两个新产生的块的元素和的乘积的分数。你想要最大化最后的总得分。
输入格式
第一行包含两个整数 (n) 和 (k)。保证 (k + 1 leq n)。
第二行包含 (n) 个非负整数 (a_1, a_2, cdots, a_n) ((0 leq a_i leq 10^4))，表示前文所述的序列。
输出格式
第一行输出你能获得的最大总得分。
第二行输出 (k) 个介于 (1) 到 (n - 1) 之间的整数，表示为了使得总得分最大，你每次操作中分开两个块的位置。第 (i) 个整数 (s_i) 表示第 (i) 次操作将在 (s_i) 和 (s_{i + 1}) 之间把块分开。
如果有多种方案使得总得分最大，输出任意一种方案即可。
限制与约定
第一个子任务共 (11) 分，满足 (1 leq k < n leq 10)。
第二个子任务共 (11) 分，满足 (1 leq k < n leq 50)。
第三个子任务共 (11) 分，满足 (1 leq k < n leq 200)。
第四个子任务共 (17) 分，满足 (2 leq n leq 1000, 1 leq k leq min{n - 1, 200})。
第五个子任务共 (21) 分，满足 (2 leq n leq 10000, 1 leq k leq min{n - 1, 200})。
第六个子任务共 (29) 分，满足 (2 leq n leq 100000, 1 leq k leq min{n - 1, 200})。
首先可以通过数学归纳法证明: 只要切割位置相同, 切割顺序不会影响答案.
首先有一个 (拿衣服) 的想法 直接想到正解的大佬可以跳过:
用 (i) 表示当前的位置, (k) 表示切割的次数, 枚举之前的每一个状态 (j).
但是由于它太 (拿衣服) 了, 所以不好处理(实际可做).
反向考虑整个序列, 转移方程变形为:
看数据 (1e6), (Oleft(n^2k
ight)) 显然不可做, 凭感觉考虑斜率优化
设 (Fleft(i, k ight) = F(i)), $Fleft(i, k-1 ight) = G(i) $ , 进行移项, 有:
斜率 (-S(i)) 单调递减.
考虑当前决策 (j) 和前一个决策 (j-1), 若 (j) 优于 (j-1), 有:
- 注意 (k) 是负值.
即:
然后就可以大力斜率优化并WA掉
注意一个细节: (a_i) 可能为 (0), 上式的分母可能为 (0), 需要在程序中特判一下.
代码:
# include <iostream>
# include <cstdio>
# include <deque>
# define LL long long
# define MAXN 1000005
using namespace std;
LL a[MAXN], sum[MAXN];
LL f[MAXN][2];
int sol[MAXN][205]; // 记录转移顺序
int q[MAXN];
double slope(int i,int j, int g) {
if(sum[i]==sum[j]) return -1e18;
return 1.0*((f[i][g]-sum[i]*sum[i])-(f[j][g]-sum[j]*sum[j]))/(sum[j]-sum[i]);
}
int main(){
int n, S;
scanf("%d%d", &n, &S);
for(int i = 1; i <= n; i++){
scanf("%lld", &a[i]);
sum[i] = a[i] + sum[i-1];
}
for(int k = 0, lim = 1; lim <= S; k^=1, lim++){
int l = 1, r = 0;
q[++r] = 0;
for(int i = 1; i <= n; i++){
int g = k^1;
while(l < r && slope(q[l], q[l+1], g)<=sum[i]){
l++;
}
f[i][k] = f[q[l]][g]+sum[q[l]]*(sum[i]-sum[q[l]]);
sol[i][lim] = q[l];
while(l < r && slope(q[r-1],q[r], g)>=slope(q[r],i, g)){
r--;
}
q[++r] = i;
}
}
printf("%lld
", max(f[n][1], f[n][0]));
for(int x=n,i=S;i>=1;--i){
x=sol[x][i];
printf("%d%c",x,"
"[i==1]);
}
return 0;
}
时间复杂度: (O(nk))
玄学 (1): 最开始写的 deque 的时候莫名其妙赤橙黄绿青蓝紫, 改手写单调队列就过了 估计是我哪写错了
玄学 (2): 本来打算移项逃避精度问题的, 结果锅掉 估计就是式子移错了