首页 > 代码库 > 【BZOJ3156】防御准备 斜率优化
【BZOJ3156】防御准备 斜率优化
【BZOJ3156】防御准备
Description
.jpg)
Input
第一行为一个整数N表示战线的总长度。
第二行N个整数，第i个整数表示在位置i放置守卫塔的花费Ai。
Output
共一个整数，表示最小的战线花费值。
Sample Input
10
2 3 1 5 4 5 6 3 1 2
2 3 1 5 4 5 6 3 1 2
Sample Output
18
HINT
1<=N<=10^6,1<=Ai<=10^9
题解：一眼看出斜率优化DP，先列出方程再说
整理一下，发现求的是下凸包，且点的坐标单调不减
题目图片太大导致不能再加图片了好气~
#include <cstdio>
#include <iostream>
#include <cstring>
#define y(_) (f[_]+_*(_+1)/2)
using namespace std;
typedef long long ll;
const int maxn=1000010;
int n;
ll q[maxn],h,t;
ll a[maxn],f[maxn];
int main()
{
scanf("%d",&n);
ll i;
for(i=1;i<=n;i++) scanf("%lld",&a[i]);
h=t=1;
for(i=1;i<=n;i++)
{
while(h<t&&(y(q[h+1])-y(q[h]))<=i*(q[h+1]-q[h])) h++;
f[i]=f[q[h]]+(i-q[h])*(i-q[h]-1)/2+a[i];
while(h<t&&(y(q[t])-y(q[t-1]))*(i-q[t])>=(y(i)-y(q[t]))*(q[t]-q[t-1])) t--;
q[++t]=i;
}
printf("%lld",f[n]);
return 0;
}
【BZOJ3156】防御准备 斜率优化
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。