Description
小H最近迷上了一个分隔序列的游戏。在这个游戏里，小H需要将一个长度为n的非负整数序列分割成k+1个非空的子序列。为了得到k+1个子序列，小H需要重复k次以下的步骤：
1.小H首先选择一个长度超过1的序列（一开始小H只有一个长度为n的序列——也就是一开始得到的整个序列）；
2.选择一个位置，并通过这个位置将这个序列分割成连续的两个非空的新序列。
每次进行上述步骤之后，小H将会得到一定的分数。这个分数为两个新序列中元素和的乘积。小H希望选择一种最佳的分割方式，使得k轮之后，小H的总得分最大。
随手列个柿子就会发现断点的选择顺序对于答案是没有影响的
\(f_{ij}\)表示前i个数字里加了j个断点的最大贡献
\[f_{i,j}=max(f_{i-1,k}+sum_k\times (sum_i-sum_k))(k< i)\]
设\(f\)表示\(f_{i-1}\)（。。。
那么对于\(k\)比\(l\)更优当且仅当
\[f_k+sum_k\times (sum_i-sum_k)>f_l+sum_l\times (sum_i-sum_l)\]
\[s_i>\frac{sum_l^2-sum_k^2+f_l-f_k}{s_l-s_k}\]
斜率优化！！
#include#include #include #define M 110001#define LL long long using namespace std;int u,m,n,k,q[M],t,h,pre[M][210];LL f[2][M],s[M];double xl(int k,int l,int u){ if(s[k]==s[l]) return -1e18; return (1.0*(long double)(-f[u][l]+f[u][k]-((long double)s[k]*s[k])+((long double)s[l]*s[l]))*1.0/((long double)1.0*(-s[k]+s[l])));}int main(){ scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) scanf("%d",&m),s[i]=(LL)s[i-1]+m; for(int j=1;j<=k;j++) { h=t=0; u=j&1; for(int i=1;i<=n;i++) { while(t>h && xl(q[h+1],q[h],!u)<=(long double)s[i]) h++; int x=q[h]; pre[i][j]=x; f[u][i]=f[!u][x]+s[x]*(s[i]-s[x]); while(t>h && xl(q[t],q[t-1],!u)>=xl(i,q[t],!u)) t--; q[++t]=i; } } printf("%lld\n",f[k&1][n]); LL x=n; for(LL i=k;i>=1;i--) { printf("%lld ",pre[x][i]); x=pre[x][i]; }}