[BZOJ 1010][HNOI 2008]玩具装箱toy【DP+斜率优化+单调队列】

  • 2018-01-26
  • 0
  • 0

Problem:

Time Limit: 1 Sec  Memory Limit: 162 MB

Description

  P教授要去看奥运,但是他舍不下他的玩具,于是他决定把所有的玩具运到北京。他使用自己的压缩器进行压缩,其可以将任意物品变成一堆,再放到一种特殊的一维容器中。P教授有编号为1...N的N件玩具,第i件玩具经过压缩后变成一维长度为Ci.为了方便整理,P教授要求在一个一维容器中的玩具编号是连续的。同时如果一个一维容器中有多个玩具,那么两件玩具之间要加入一个单位长度的填充物,形式地说如果将第i件玩具到第j个玩具放到一个容器中,那么容器的长度将为 x=j-i+Sigma(Ck) i<=K<=j 制作容器的费用与容器的长度有关,根据教授研究,如果容器长度为x,其制作费用为(X-L)^2.其中L是一个常量。P教授不关心容器的数目,他可以制作出任意长度的容器,甚至超过L。但他希望费用最小.

Input

  第一行输入两个整数N,L.接下来N行输入Ci.1<=N<=50000,1<=L,Ci<=10^7

Output

  输出最小费用

Sample Input

5 4
3
4
2
1
4

Sample Output

1

HINT

Source

Solution:

本题与[HDU 3507] Print Article【DP+斜率优化+单调队列】很相似。

令 dp[i] 为前 i 个玩具装箱的最小费用,sum[i] 为 C[i] 的前缀和,则

  • dp[ i ] = min{ dp[ j ] + ( sum[ i ] - sum[ j ] + i - j - 1 - L)2 }, 其中 0 ≤ j < i

又令 S[i] = sum[i] + iK = L + 1,则

  • dp[ i ] = min{ dp[ j ] + ( S[ i ] - S[ j ] - K )2 }, 其中 0 ≤ j < i

证明决策单调性略。

设在状态 i 中,决策 k ( k > j ) 较决策 j 更优,则将两个决策点的比较式转化为斜率式得:

  • ( dp[ k ] - dp[ j ] + ( S[ k ] + K )2 - ( S[ j ] + K )2 ) / (2 S[ k ] - 2 S[ j ] ) ≤ S[ i ]

即可将复杂度优化到 O(N)

推荐几个不错的博客:

Code: O(N) [2464K, 136MS]

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#define sqr(x) ((x) * (x))
using namespace std;
typedef long long ll;

int N, L, a[50005];
ll C, S[50005];
int q[50005], fr, re;
ll dp[50005];

inline double dx(const int &j, const int &k) {return S[k] - S[j] << 1;}

inline double dy(const int &j, const int &k) {return dp[k] - dp[j] + sqr(S[k] + C) - sqr(S[j] + C);}

int main(){
	scanf("%d%d", &N, &L), C = L + 1;
	for(register int i = 1; i <= N; i++)
		scanf("%d", a + i), S[i] = S[i - 1] + a[i] + 1;
	fr = re = 0, q[re++] = 0;
	for(register int i = 1; i <= N; i++){
		while(fr + 1 < re && dy(q[fr], q[fr + 1]) <= dx(q[fr], q[fr + 1]) * S[i]) fr++;
		dp[i] = dp[q[fr]] + sqr(S[i] - S[q[fr]] - C);
		while(fr + 1 < re && dy(q[re - 1], i) * dx(q[re - 2], q[re - 1]) <= dy(q[re - 2], q[re - 1]) * dx(q[re - 1], i)) re--;
		q[re++] = i;
	}
	printf("%lld\n", dp[N]);
	return 0;
}

评论

还没有任何评论,你来说两句吧



常年不在线的QQ:
49750

不定期更新的GitHub:
https://github.com/Darkleafin


OPEN AT 2017.12.10

如遇到代码不能正常显示的情况,请刷新页面。
If the code cannot be displayed normally, please refresh the page.


发现一个优美的网站:
https://visualgo.net/en
















- Theme by Qzhai