【BZOJ1010】【HNOI2008】玩具装箱toy (斜率优化DP) 解题报告

题目：

题目在这里

思路与做法：

这题不难想。

首先我们先推出一个普通的dp方程：

$f_i = min \{ f_j+(i-j-1+sum_i-sum_j-L)^2\}$

然后就推一推式子了：

我们来比较计算f[i]时的j和k两个决策

$f_j+(i-j-1+sum_i-sum_j-L)^2 < f_k+(i-k-1+sum_i-sum_k-L)^2$

令$num_i = i+sum_i$

令$C = L+1$

$f_j+(num_i-num_j-L-1)^2 < f_k+(num_i-num_j-L-1)^2$

$f_j+{num_i}^2-2*num_i*(num_j+C)+(num_j+C)^2$

$<f_k+{num_i}^2-2*num_i*(num_k+C)+(num_k+C)^2$

$f_j+(num_j+C)^{2-f_k-(num_k+C)}2 < $

$2*num_i*(num_j-num_k)$

${f_j+(num_j+C)^2-f_k-(num_k+C)^2 \over 2*(num_j-num_k)} < num_i$

接下来就可以用斜率优化dp了。

代码：

#include <iostream>

#include <cstdlib>

#include <cstdio>

#include <cstring>

using namespace std;

const int N = 50010;

inline long long sqr(long long x) { return x*x; }

long long a[N];

long long sum[N];

long long num[N], C;

long long f[N];

double calc(int j, int k) { return (double)(f[j]+sqr(num[j]+C)-f[k]-sqr(num[k]+C))/(double)(2*(num[j]-num[k])); }

int Q[N], hd, tl;

int main()

{   int n;

	long long m;

	scanf("%d%lld", &n, &m);

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

	{   scanf("%lld", &a[i]);

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

	}

	for(int i=1; i<=n; i++) num[i] = sum[i]+i;

	C = m+1;

	Q[hd = 0] = 0;

	tl = 1;

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

	{   while(hd < tl-1 && calc(Q[hd+1], Q[hd]) <= num[i]) hd++;

		f[i] = f[Q[hd]] + sqr(num[i]-num[Q[hd]]-C);

		while(hd < tl-1 && calc(i, Q[tl-1]) <= calc(Q[tl-1], Q[tl-2])) tl--;

		Q[tl++] = i;

	}

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

	return 0;

}

巴特西

【BZOJ1010】【HNOI2008】玩具装箱toy (斜率优化DP) 解题报告

题目：

思路与做法：

代码：

最新文章

热门文章