codeforces 1175D. Array Splitting

cf传送门
vjudge传送门


首先，人人都能想到一个很显然的dp做法：令(dp[i][j])表示前(i)个数分成(j)段的最大划分价值，于是有(dp[i][j] = max {dp[i-1][j], dp[i-1][j-1] } + a[i]*j).
但这样(O(n^2))妥妥的不能优化，没了。


然后我不知咋的就想到了这么个思路：
如果(k=1)，那么答案就是所有(a[i])之和。
接下来假如在(i)出划分成新的两段，对答案的贡献就是(sum_{j=i}^{n}a[j])，即后缀和(sum'[i])。
又因为每一个元素只能出现在两个连续子序列里，那么只要选前(k-1)大的后缀和就好啦。


需要注意的是(sum'[1])一定要选，因此除了(sum'[1])要再选(k-1)个。

#include<cstdio>
#include<algorithm>
#include<cctype>
using namespace std;
#define enter puts("") 
#define space putchar(' ')
#define In inline
typedef long long ll;
const int maxn = 3e5 + 5;
In ll read()
{
	ll ans = 0;
	char ch = getchar(), las = ' ';
	while(!isdigit(ch)) las = ch, ch = getchar();
	while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
	if(las == '-') ans = -ans;
	return ans;
}
In void write(ll x)
{
	if(x < 0) x = -x, putchar('-');
	if(x >= 10) write(x / 10);
	putchar(x % 10 + '0');
}

int n, K, a[maxn];
ll sum[maxn], ans = 0;

int main()
{
//	MYFILE();
	n = read(), K = read();
	for(int i = 1; i <= n; ++i) a[i] = read();
	if(n == 1) {write(a[1]), enter; return 0;}
	for(int i = n; i > 1; --i)
	{
		sum[i] = sum[i + 1] + a[i];
		ans += a[i];
	}
	ans += a[1];
	sort(sum + 2, sum + n + 1, [&](ll a, ll b) {return a > b;});
	for(int i = 2; i <= K; ++i) ans += sum[i];
	write(ans), enter;
	return 0;
}