cf1175D.ArraySplitting(将数组分成k部分所有数的值*他所在的第几个部分和最大拆式子)

题目

我就是个弱智。哭了。唉。怎么就是想不到拆开式子呢? 拆开之后很简单。

sum&＃61;s[r1]*1&＃43;(s[r2]-s[r1])*2&＃43;(s[r3]-s[r2])*3&＃43;....&＃43;(s[rk-1]-s[rk-2])*(k-1)&＃43;(s[n]-s[rk-1])*k;
把括号打开
sum&＃61;k*s[n]-s[r1]-s[r2]-...s[rk-1];
为了使sum尽可能大就选前k-1个前缀和即可
那么就对前缀和有小到大排序。。
前k-1个前缀和直接对前缀sum数组排序即可。就没有打乱顺序&＃xff0c;就是按排序后的为k-1个分界点。


#include
#define m(a,b) memset(a,b,sizeof a)
using namespace std;
typedef long long ll;
const int N&＃61;3e5&＃43;5;
ll sum[N];
int main(){int n,k;scanf("%d%d",&n,&k);for(int i&＃61;1,x;i<&＃61;n;&＃43;&＃43;i) scanf("%d",&x),sum[i]&＃61;sum[i-1]&＃43;x;ll ans&＃61;(ll)k*sum[n];sort(sum&＃43;1,sum&＃43;n-1&＃43;1);--k;for(int i&＃61;1;k;--k,&＃43;&＃43;i) ans-&＃61;sum[i];printf("%lld\n",ans);
}