《P3648 [APIO2014] 序列分割》

题目描述

你正在玩一个关于长度为 n 的非负整数序列的游戏。这个游戏中你需要把序列分成 k+1 个非空的块。为了得到 k+1 块，你需要重复下面的操作 k 次：

选择一个有超过一个元素的块（初始时你只有一块，即整个序列）。

选择两个相邻元素把这个块从中间分开，得到两个非空的块。

每次操作后你将获得那两个新产生的块的元素和的乘积的分数。你想要最大化最后的总得分。

输入格式

第一行包含两个整数 n 和 k。保证 k+1≤n。

第二行包含 n 个非负整数 a1​,a2​,⋯,an​ (0≤ai​≤104)，表示前文所述的序列。

输出格式

第一行输出你能获得的最大总得分。

第二行输出 k 个介于 1 到 n−1 之间的整数，表示为了使得总得分最大，你每次操作中分开两个块的位置。第 i 个整数 si​ 表示第 i 次操作将在 si​ 和 si​+1 之间把块分开。

如果有多种方案使得总得分最大，输出任意一种方案即可。

输入输出样例

输入 #1复制

7 3 4 1 3 4 0 2 3

输出 #1复制

108 1 3 5

说明/提示

你可以通过下面这些操作获得 108 分：

初始时你有一块 (4,1,3,4,0,2,3)。在第 1 个元素后面分开，获得 4×(1+3+4+0+2+3)=52 分。

你现在有两块 (4),(1,3,4,0,2,3)。在第 3 个元素后面分开，获得 (1+3)×(4+0+2+3)=36 分。

你现在有三块 (4),(1,3),(4,0,2,3)。在第 5 个元素后面分开，获得 (4+0)×(2+3)=20 分。

所以，经过这些操作后你可以获得四块 (4),(1,3),(4,0),(2,3) 并获得 52+36+20=108 分。

【限制与约定】

第一个子任务共 11 分，满足 1≤k<n≤10。

第二个子任务共 11 分，满足 1≤k<n≤50。

第三个子任务共 11 分，满足 1≤k<n≤200。

第四个子任务共 17 分，满足 2≤n≤1000,1≤k≤min{n−1,200}。

第五个子任务共 21 分，满足 2≤n≤10000,1≤k≤min{n−1,200}。

第六个子任务共 29 分，满足 2≤n≤100000,1≤k≤min{n−1,200}。

感谢 @larryzhong 提供的加强数据。

代码实现：

#include<bits/stdc++.h> using namespace std; #define reg register ll #define ll long long #define inf 0x3f3f3f3f inline ll rd(){ ll s=0,w=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();} while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar(); return s*w; } const ll K=300+10; const ll N=1e5+10; ll dp[2][N],s[N]; ll p[K][N],q[N]; inline double slp(ll x,ll y,ll l){ if(s[x]==s[y])return -1e18; return ((s[x]*s[x]-dp[l&1^1][x])-(s[y]*s[y]-dp[l&1^1][y]))/(1.0*(s[x]-s[y])); } int main(){ ll n=rd(),k=rd(); for(reg i=1;i<=n;i++) s[i]=s[i-1]+rd(); for(reg i=1;i<=k;i++){ ll h=0,t=0; for(reg j=1;j<=n;j++){ while(h<t&&slp(q[h],q[h+1],i)<=s[j])h++; ll tmp=q[h]; dp[i&1][j]=dp[i&1^1][q[h]]+s[q[h]]*(s[j]-s[q[h]]); p[i][j]=q[h]; while(h<t&&slp(q[t],j,i)<=slp(q[t-1],q[t],i))t--; q[++t]=j; } } printf("%lld\n",dp[k&1][n]); ll x=n; for(reg i=k;i>=1;i--){ x=p[i][x]; printf("%lld ",x); } return 0; }