BZOJ3156 防御准备(动态规划+斜率优化)
2024-08-28 07:22:09
设f[i]为在i放置守卫塔时1~i的最小花费。那么显然f[i]=min(f[j]+(i-j)*(i-j-1)/2)+a[i]。
显然这是个斜率优化入门题。将不与i、j同时相关的提出,得f[i]=min(f[j]+j*(j+1)/2-ij)+i*(i-1)/2+a[i]。
套路地,假设j>k且j转移优于k,则f[j]+j*(j+1)/2-ij<f[k]+k*(k+1)/2-ik,(f[j]+j*(j+1)/2-f[k]-k*(k+1)/2)/(j-k)<i。
维护下凸壳即可。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int read()
{
int x=,f=;char c=getchar();
while (c<''||c>'') {if (c=='-') f=-;c=getchar();}
while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();
return x*f;
}
#define N 1000010
#define ll long long
int n,a[N],q[N];
ll f[N];
long double calc(int j,int k)
{
return (long double)(f[j]+(1ll*j*(j+)>>)-f[k]-(1ll*k*(k+)>>))/(j-k);
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("bzoj3156.in","r",stdin);
freopen("bzoj3156.out","w",stdout);
const char LL[]="%I64d\n";
#else
const char LL[]="%lld\n";
#endif
n=read();
for (int i=;i<=n;i++) a[i]=read();
f[]=;
int head=,tail=;q[]=;
for (int i=;i<=n;i++)
{
while (head<tail&&calc(q[head],q[head+])<i) head++;
f[i]=f[q[head]]+(1ll*q[head]*(q[head]+)>>)-1ll*i*q[head]+(1ll*i*(i-)>>)+a[i];
while (head<tail&&calc(q[tail-],q[tail])>calc(q[tail],i)) tail--;
q[++tail]=i;
}
cout<<f[n];
return ;
}
最新文章
- proteus 运行出错,用户名不可使用中文!
- 分享php中四种webservice实现的简单架构方法及实例
- Java当中的I/O的字符流
- Go语言相关图书推荐
- android 三种弹出框之一PopupWindow
- 在IT学习中的“认识论”
- SQL*Net message to client
- 关于接口使用getType的方法的问题
- 【剑指offer】面试题24:二叉搜索树的后序遍历序列
- js函数收藏:获取cookie值
- ASP.NET MVC 4.0的Action Filter
- python中的嵌套类(内部类调用外部类中的方法函数)
- FullScreenFragment Code
- Linux 安装配置 Tomcat
- django框架配置mysql数据库
- Java基础随记-不定时更新
- 洛谷P1897电梯里的爱情题解
- OpenGL——旋转的六边形(动画)
- j解决sparkr中使用某些r的原生函数 发生错误Error: class(objId) == ";jobj"; is not TRUE的问题
- Android-系统解析AndroidManifest