洛谷 P3195 [HNOI2008]玩具装箱TOY

题意简述

有n个物体，第i个长度为ci

将n个物体分为若干组，每组必须连续

如果把i到j的物品分到一组，则该组长度为 \( j - i + \sum\limits_{k = i}^{j}ck \)

求最小花费

题解思路

\( dp[i] = min(dp[j] + (i - j - 1 + \sum\limits_{k = i}^{j}ck)) \)

然后斜率优化，单调队列维护

代码

#include <cstdio>

using namespace std;

typedef long long ll;

int n, l, h, t;

int q[50010];

ll sum[50010], dp[50010];

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

int s1(int x) {return sum[x] + x; }

int s2(int x) {return s1(x) + l + 1; }

double calc(int i, int j) {return (double)(sqr(s2(i)) + dp[i] - sqr(s2(j)) - dp[j]) / (s1(i) - s1(j)); }

int main()

{

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

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

	{

		scanf("%d", &sum[i]);

		sum[i] += sum[i - 1];

	}

	h = t = 1;

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

	{

		while (h < t && calc(q[h], q[h + 1]) <= 2 * s1(i)) ++h;

		dp[i] = dp[q[h]] + sqr(i - q[h] - 1 + sum[i] - sum[q[h]] - l);

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

		q[++t] = i;

	}

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

}

巴特西

洛谷 P3195 [HNOI2008]玩具装箱TOY

题意简述

题解思路

代码

最新文章

热门文章