【Luogu】P3195玩具装箱(斜率优化DP)
2024-09-08 00:15:19
这题还是比较炫的
我们设f[i]是已经装了前i个玩具,且第i个玩具是某箱子里装的最后一个东西(废话)
那我们很轻松可以想到一个转移方程
for(int i=;i<=n;++i)
for(int j=;j<i;++j)
f[i]=min(f[i],f[j]+squa(sum[i]-sum[j]+i-j--L)
其中sum是玩具长度的前缀和,squa是平方。
但是O(50000*50000)瞬间爆炸
我们设f[i]是由f[j]转移过来的,j是最优转移,同时还有一个不那么优的转移k
那肯定有\(f[j]+squa(sum[i]-sum[j]+i-j-1-L)<f[k]+squa(c[i]-c[k]+i-k-1-L)\)
我们设\(M=sum[i]-1-L,T[j]=sum[j]+j\)
容易发现M只和i有关,T只和j有关
然后\(f[j]+squa(M-T[j])<f[k]+squa(M-T[k])\)
两边平方和展开划一划得到
\(((f[j]+squa(T[j]))-(f[k]+squa(T[k])))/(2*(T[j]-T[k]))>M\)
注意到f,T,M都是单调的
于是可以单调队列斜率优化
为什么是斜率优化呢?因为左面那个大于M的东西看着像斜率啊
233
附上一个讲斜率优化的博客
代码
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<algorithm>
#include<iostream> using namespace std; inline long long read(){
long long num=,f=;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') f=-;
ch=getchar();
}
while(isdigit(ch)){
num=num*+ch-'';
ch=getchar();
}
return num*f;
} long long f[];
long long M[];
long long T[];
long long c[];
int s[],h,t;
inline long long squa(long long a){ return a*a; }
inline long long count(int x,int y){ return ((f[x]+squa(T[x]))-(f[y]+squa(T[y])))/(*(T[x]-T[y])); } int main(){
int n=read(),l=read();
for(int i=;i<=n;++i){
c[i]=read()+c[i-];
f[i]=1e18;
T[i]=c[i]+i;
M[i]=c[i]+i-l-;
}
for(int i=;i<=n;++i){
while(h<t&&count(s[h],s[h+])<=M[i]) h++;
int x=s[h];
f[i]=f[x]+squa(M[i]-T[x]);
while(h<t&&count(s[t-],s[t])>=count(s[t],i)) t--;
s[++t]=i;
}
printf("%lld",f[n]);
return ;
}
最新文章
- call经常用到的地方
- Python之路,day6-Python基础
- 浅析tomcat nio 配置
- Mini projects #3 ---- Stopwatch: The Game
- SQL Pass北京举行2014年第一次线下活动
- C#(Winform) Http 发送数据
- java 之 对象与垃圾回收
- Netty ChannelOption 解释
- Java类加载器深入理解
- 百度全站变https
- java枚举细节
- React 系列文章(1): npm 手动搭建React 运行实例 (新手必看)
- 【一天一道LeetCode】#52. N-Queens II
- bs4抓取糗事百科
- HTML学习笔记Day1
- jQuery.event详细解析
- Ruby on Rails Mountable vs. Full Engine
- sql update set from 的用法 (转)
- 基于tomcat7 web开发中的一点小东西
- AOP AspectJ注解