洛谷 P3648 [APIO2014]序列分割

题意简述

有一个长度为n的序列，分成k + 1非空的块，

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

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

题解思路

f[p][i]=max(f[p−1][j]+sum[j]×(sum[i]−sum[j]))

可以用斜率优化

代码

#include <cstdio>

using namespace std;

typedef long long ll;

int n, k, l, h, t;

int q[110000];

int ans[210][110000];

ll sum[110000];

ll dp[2][110000];

ll sqr(ll x) {return x * x; }

double calc(int i, int j, int l)

{

	if (sum[i] == sum[j]) return -1e18;

	return (dp[l & 1 ^ 1][j] - sqr(sum[j]) - dp[l & 1 ^ 1][i] + sqr(sum[i])) * 1.0 / (sum[i] - sum[j]);

}

int main()

{

	scanf("%d%d", &n, &k);

	for (register int i = 1; i <= n; ++i) scanf("%d", &sum[i]), sum[i] += sum[i - 1];

	for (register int l = 1; l <= k; ++l)

	{

		h = t = 0;

		for (register int i = 1; i <= n; ++i)

		{

			while (h < t && calc(q[h], q[h + 1], l) <= sum[i]) ++h;

			dp[l & 1][i] = dp[l & 1 ^ 1][q[h]] + sum[q[h]] * (sum[i] - sum[q[h]]);

			ans[l][i] = q[h];

			while (h < t && calc(q[t - 1], q[t], l) >= calc(q[t], i, l)) --t;

			q[++t] = i;

		}

	}

	printf("%lld\n", dp[k & 1][n]);

	for (register int i = k, s = n; i >= 1; --i)

		printf("%d ", s = ans[i][s]);

}

巴特西

洛谷 P3648 [APIO2014]序列分割

题意简述

题解思路

代码

最新文章

热门文章