APIO2014 序列分割
k个划分点
显然对于给定的一组划分点，任意两个不在同一个块的\(i,j\)都会对答案产生\(A_iA_j\)的贡献，就可以不用考虑划分点的顺序了。
由于\(k\le 200\)，可以直接k次斜率优化DP\(O(nk)\)解决，但是这样不够优美！要把\(k\le 200\)去掉就过不了了！
由于k越大答案越大，我们还可以通过凸优化解决。
设一个mid，对于每一次划分都要付出mid的代价，然后直接斜率优化DP最大答案，并且记录达到这个dp值的最小划分块数。随着mid增加，最小划分块数会不增。
找到最大满足最小划分块数<=k+1的mid。这个显然可以二分。
然后dp以后输出dp值+k*mid就可以解决不要输出方案的问题了。
但是方案是真的难输出
记录前i个元素，划分使得答案为dp[i]划分次数的最小值和最大值。以及能得到dp[i] 以i为右端点块的所有左端点。
然后对于\(A_i=0\)要特别考虑。
比较难调。
/*
Author: CNYALI_LK
LANG: C++
PROG: 3648.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
#define x first
#define y second
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
//typedef long long ll;
typedef long long ll;
typedef pair<ll,ll> pii;
template<class T>ll chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>ll chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
template<class T>ll dcmp(T a,T b){return a>b;}
template<ll *a>ll cmp_a(ll x,ll y){return a[x]<a[y];}
#define min mmin
#define max mmax
#define abs aabs
ll read(){
ll s=0,base=1;
char c;
while(!isdigit(c=getchar()))if(c=='-')base=-base;
while(isdigit(c)){s=s*10+(c^48);c=getchar();}
return s*base;
}
ll a[102423],s[102423],f[102423],g[102423],n,mn[102423],mx[102423];
vector<ll> lst[102423];
pii q[102423],*l,*r;
void Top(ll w,ll bt){
while(l<r && ((l+1)->y-l->y)<w*(s[(l+1)->x]-s[l->x]))++l;
f[bt]=s[l->x]*w-l->y;
mn[bt]=mn[l->x]+1;
lst[bt].clear();
while(l<r && ((l+1)->y-l->y)==w*(s[(l+1)->x]-s[l->x])){
lst[bt].push_back(l->x);
++l;
}
mx[bt]=mx[l->x]+1;
lst[bt].push_back(l->x);
}
void Push(pii a){
while(l<r && (a.y-r->y)*(s[a.x]-s[(r-1)->x])<(a.y-(r-1)->y)*(s[a.x]-s[r->x]))--r;
*(++r)=a;
}
ll dp(ll w){
l=r=q;
pii *Xans;
for(ll i=1;i<=n;++i){
if(!a[i]){
mn[i]=mn[i-1];
if(!w){
mx[i]=mx[i-1]+1;
lst[i].clear();
lst[i].push_back(i-1);
}
else{
mx[i]=mx[i-1];
lst[i].clear();
}
f[i]=f[i-1];
}else{
Push(make_pair(i-1,s[i-1]*s[i-1]-f[i-1]));
Top(s[i],i);
f[i]-=w;
}
}
return mn[n];
}
void Out(ll x,ll times,ll out){
while(x && !a[x] && mx[x-1]>=times)--x;
if(!x)return;
--times;
for(auto i:lst[x]){
if(mn[i]<=times && times<=mx[i]){
Out(i,times,1);break;
}
}
if(out)printf("%lld ",x);
}
int main(){
#ifdef cnyali_lk
freopen("3648.in","r",stdin);
freopen("3648.out","w",stdout);
#endif
ll k,l,r,mid;
n=read();
k=read()+1;
for(ll i=1;i<=n;++i){
a[i]=read();
s[i]=s[i-1]+a[i];
}//*
l=0,r=1e18;
while(l<=r){
mid=(l+r)>>1;
if(dp(mid)>k)l=mid+1;
else r=mid-1;
}
//*/
mid=r+1;
dp(mid);
printf("%lld\n",f[n]+mid*k);
Out(n,k,0);
putchar('\n');
return 0;
}