BZOJ 1010 [HNOI2008]toy 玩具装箱
2017.6.9:经过我的不懈努力,终于把此题A掉了,但上凸和下凸总是那么让人费解……
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
以下摘自YYF的blog:
先推出普通dp的方程
f[i] = min{f[j] + (sum[i] - sum[j] + i - j - 1 - L)2}
这方程明显是O(n2)级别的,再看看这卖萌的数据范围,不用质疑,铁定超时。还是来考虑一下优化(例如斜率优化)吧。由于这方程长得太丑了,于是决定简化一下
设S(i) = sum[i] + i,C = L + 1
于是方程变成了这样
f[i] = min{f[j] + (S(i) - S(j) - C)2}
现在假设在状态i之前有两个可以转移到i的两个状态j, k(j < k),现在使j比k更优,那么它要满足
f[j] + (S(i) - S(j) - C)2 < f[k] + (S(i) - S(k) - C)2
看平方不爽,而且无法化简,果断完全平方公式拆掉
f[j] + [S(i) - (S(j) + C)]2 < f[k] + [S(i) - (S(k) + C)]2
f[j] + (S(j) + C)2 - 2S(i)[S(j) + C] < f[j] + (S(k) + C)2 - 2S(i)[S(k) + C]
(其实可以一起拆掉,只不过中途有些地方可以直接"抵消")继续"拆"括号,移项
f[j] + S(j)2 + 2S(j)C - 2S(i)[S(j) - S(k)] < f[k] + S(k)2 + 2S(k)C
继续,右边只留一个和i有关的单项式
(f[j] + S(j)2 + 2S(j)C) - (f[k] + S(k)2 + 2S(k)C) < 2S(i)[S(j) - S(k)]
继续移项,右边只留和i有关的式子
注意,S(i)是单调递增,所以S(j) - S(k) < 0,移项的时候不等号方向相反,于是我们愉快地得到了斜率方程(干什么?斜率优化去掉一个n)。
对于状态i,用(f[i] + S(i)2 + 2S(i)C)作纵坐标,2S(i)作横坐标,删掉上凸点,维护一条斜率递增的折线即可。
/**************************************************************
Problem: 1010
User: Doggu
Language: C++
Result: Accepted
Time:100 ms
Memory:1992 kb
****************************************************************/ #include <cstdio>
#include <algorithm>
template<class T>inline void readin(T &res) {
static char ch;
while((ch=getchar())<''||ch>'');
res=ch-;while((ch=getchar())>=''&&ch<='')res=(res<<)+(res<<)+ch-;
}
const int N = ;
long long n, C, S[N], f[N], head, tail, q[N];
#define Y(k) (f[(k)]+S[(k)]*S[(k)]+2*C*S[(k)])
#define X(k) (S[(k)])
int main() {
readin(n);readin(C);C++;
for( int i = ; i <= n; i++ ) readin(S[i]),S[i]+=S[i-];
for( int i = ; i <= n; i++ ) S[i]+=i;
head=tail=;q[tail++]=;
for( int i = ; i <= n; i++ ) {
while(tail-head>&&Y(q[head])-Y(q[head+])>=*S[i]*(X(q[head])-X(q[head+]))) head++;
f[i]=f[q[head]]+(S[i]-S[q[head]]-C)*(S[i]-S[q[head]]-C);
while(tail-head>&&(Y(q[tail-])-Y(q[tail-]))*(X(i)-X(q[tail-]))>=(X(q[tail-])-X(q[tail-]))*(Y(i)-Y(q[tail-]))) tail--;//若维护"="
q[tail++]=i;
}
printf("%lld\n",f[n]);
return ;
}
DP斜率优化
最新文章
- MindManager中发送导图给别的用户的教程
- Xcode插件管理工具Alcatraz
- React Native知识2-Text组件
- JAVA中的TreeSet
- YTU 3026: 中序线索化二叉树
- OC知识梳理-NSArray与NSMutableArray相关知识
- 《同一个类中不同方法之间的调用相关问题(省略的类名或者this)》
- hdu 5655 CA Loves Stick
- 如何在服务(Service)程序中显示对话框
- dede版权信息修改
- 在ajax当中使用url重写来避免url的暴露
- ALAsset和ALAssetRepresentation
- Android:ViewPager04
- JQuery事件机制笔记
- Java 模拟栈结构
- PuTTY的下载安装和基本使用方法教程
- showdoc 文档管理系统
- COMCMS_CORE 起步篇,如何运行和部署
- hdu-1814(2-sat)
- stm32学习基本知识点
热门文章
- node 集群与稳定
- python之爬虫_并发(串行、多线程、多进程、异步IO)
- java工程文件路径的问题
- JSON toBean Timestamp To Date 时间戳转日期
- learning of a previous team
- c++工厂模式(Factory method)
- MapReduce编程之Map Join多种应用场景与使用
- 『编程题全队』Alpha 阶段冲刺博客集合
- utf-8编码的中文看成2个字符,其他数字字符看成一个字符
- (暂时弃坑)(半成品)ACM数论之旅18---反演定理 第二回 Mobius反演(莫比乌斯反演)((づ ̄3 ̄)づ天才第一步,雀。。。。)