1010: [HNOI2008]玩具装箱toy
Time Limit: 1 Sec Memory Limit: 162 MBSubmit: 8184 Solved: 3210
[Submit][Status][Discuss]
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
3
4
2
1
4
Sample Output
HINT
Source
time:14:30-14:43-15:06
【总结】
形象地理解斜率优化降低复杂度的原因：（％％％Tunix）
嗯我们现在就知道了对于每个状态i，从1 ~ i-1这些决策中的“当前最优决策”是有一个单调性的！假设 k 是当前枚举到的最优决策，然后我们继续枚举直到决策 j ，满足上面那个不等式！则表明决策 j 比决策 k 更优！那么有什么用呢？我们根据不等式发现，这个“更优”的属性，只跟 j 和 k 有关，与阶段 i 是无关的！也就是说，当 j 成为一个可选的方案的时候，k 就永远也不用再考虑它了，这就大大减少了转移时的决策数！从而降低了复杂度！
来自 <http://www.cnblogs.com/Tunix/p/4331099.html>
说了这么多，用队列维护斜率单调的决策序列，其实就是从左右端点分别维护一个凸包!!
具体是上凸包还是下凸包由题目中最优解是min还是max决定
数形结合的思想：
解决这类斜率优化dp的步骤：
1、求斜率方程：一般化为左边是j和k，右边是i的形式
2、规定队列的维护规则（数形结合，维护凸包）
另外，写出dp方程：1、前缀和思想 2、化为斜率优化解决的形式
【代码】
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
#define inf 1<<30
using namespace std;
const int N=100000;
typedef long long LL;
int n,L,q[N],l,r;
LL f[N],s[N],a[N];
inline int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline double slope(int j,int k)
{
return double((f[k]+s[k]*s[k])-(f[j]+s[j]*s[j]))/double(2*(s[k]-s[j]));
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("bzoj1010.txt", "r", stdin);
freopen("toy.txt", "w", stdout);
#endif
n=read();L=read()+1;
F(i,1,n){
a[i]=read()+1;
s[i]=s[i-1]+a[i];
}
F(i,1,n){
while(l<r && slope(q[l],q[l+1])<(s[i]-L)) l++;//大写L
int t=q[l];
f[i]=f[t]+(s[i]-s[t]-L)*(s[i]-s[t]-L);
while(l<r && slope(q[r-1],q[r])>slope(q[r],i)) r--;
q[++r]=i;
}
printf("%lld\n",f[n]);
return 0;
}
评论 (0)
