bzoj1911[Apio2010]特别行动队 斜率优化dp
1911: [Apio2010]特别行动队
Time Limit: 4 Sec Memory Limit: 64 MB
Submit: 5057 Solved: 2492
[Submit][Status][Discuss]
Description
Input
Output
Sample Input
-1 10 -20
2 2 3 4
Sample Output
HINT
dp[i]=dp[j]+a*x*x+b*x+c
x=sum[i]-sum[j]
证明单调性
假设对于i点 k<j且j的决策比k优
dp[j]+a*(sum[i]-sum[j])*(sum[i]-sum[j])+b*(sum[i]-sum[j])+c>=dp[k]+a*(sum[i]-sum[k])*(sum[i]-sum[k])+b*(sum[i]-sum[k])+c
化简得 dp[j]+a*sum[j]*sum[j]-2*a*sum[i]*sum[j]-b*sum[j]>=dp[k]+a*sum[k]*sum[k]-2*a*sum[i]*sum[k]-b*sum[k]
要证明单调性 需证明下面的式子
dp[j]+a*(sum[t]-sum[j])*(sum[t]-sum[j])+b*(sum[t]-sum[j])+c>=dp[k]+a*(sum[t]-sum[k])*(sum[t]-sum[k])+b*(sum[t]-sum[k])+c
化简得dp[j]+a*sum[j]*sum[j]-2*a*sum[t]*sum[j]-b*sum[j]>=dp[k]+a*sum[k]*sum[k]-2*a*sum[t]*sum[k]-b*sum[k]
设t>i 显然sum[t]>=sum[i] 设sum[t]=sum[i]+v
代入sum[t]得 dp[j]+a*sum[j]*sum[j]-2*a*sum[i]*sum[j]-b*sum[j]+v*sum[j]>=dp[k]+a*sum[k]*sum[k]-2*a*sum[i]*sum[k]-b*sum[k]+v*sum[k]
因为j>k 所以sum[j]>=k 上式成立,决策单调性得证
证毕
可以写出斜率式
dp[j]+a*sum[j]^2-2*a*sum[i]*sum[j]-b*sum[j]>=dp[k]+a*sum[k]^2-2*a*sum[i]*sum[k]-b*sum[k] 且j>k
=> dp[j]-dp[k]+a*sum[j]^2-a*sum[k]^2+b*sum[k]-b*sum[j]>=sum[i]*2*a*(sum[j]-sum[k])
=> (dp[j]-dp[k]+a*sum[j]^2-a*sum[k]^2+b*sum[k]-b*sum[j])/(2*a*(sum[j]-sum[k]))>=sum[i]
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cmath>
#include<vector>
#include<cstdlib>
#include<iostream>
#define ll long long
#define inf 2147483647
#define N 1000005
using namespace std;
ll dp[N],sum[N];
int a,b,c,q[N];
ll pw(ll x){return x*x;}ll S(int j,int k){return *a*(sum[j]-sum[k]);}
ll G(int j,int k){return dp[j]-dp[k]+a*pw(sum[j])-a*pw(sum[k])+b*sum[k]-b*sum[j];}
double slope(int j,int k){return (double)G(j,k)/S(j,k);} int main(){
int n;
scanf("%d",&n);
scanf("%d%d%d",&a,&b,&c);
for(int i=;i<=n;i++){
int x;
scanf("%d",&x);
sum[i]=sum[i-]+x;
}
int h=,t=;
for(int i=;i<=n;i++){
while(h+<t&&slope(q[h],q[h+])<=sum[i])h++;
int j=q[h],x=sum[i]-sum[j];
dp[i]=dp[j]+a*pw(x)+b*x+c;
while(h+<t&&slope(i,q[t-])<=slope(q[t-],q[t-]))t--;
q[t++]=i;
}
printf("%lld",dp[n]);
return ;
}
最新文章
- php入门,配置wampserver
- Elastislide - 响应式的图片循环展示效果
- webSocket ws协议测试
- 问题导向VS目标导向:领导者要倾向哪种?
- ubuntu+php5.6+redis+mysql5.5+nginx
- bootstrap插件学习-bootstrap.carousel.js
- Object C学习笔记18-SEL,@ selector,Class,@class
- Unity shader(CG) 写一个 散色、折射、反射、菲涅尔、gamma、简单后期屏幕特效
- Eclipse代码风格设置
- ASP.NET后台自定义导出Excel
- 444A/CF
- Swift\本地文件管理
- Linux系统运维工程该具备哪些素质
- Entity Framework Core 2.0 新特性
- mysql 常用函数总结
- linux基本命令学习01
- 手写JAVA虚拟机(二)——实现java命令行
- (最详细)小米MIX的Usb调试模式在哪里打开的教程
- IOPLL动态重配
- redis安装命令