[BZOJ3156]防御准备(动态规划,斜率优化)

发布于 2018-04-08  79 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ3156]防御准备(动态规划,斜率优化)

Description

BZOJ3156

Tag

动态规划,斜率优化

解决思路

设F[i]表示前i个检查点并且强制在i这里设置一个检查点的最小花费,那么有
\[F[i]=min(F[j]+(i-j)*(i-j-1)/2)+Cost[i]\]
里面是一个可以斜率优化的式子,化成斜率形式
\[F[j]+\frac{1}{2}j^2+\frac{1}{2}j=ij-Cost[i]+F[i]+\frac{1}{2}i-\frac{1}{2}i^2\]
那么现在的任务就是要最小化截距,由于斜率和i都是递增的,所以维护一个下凸壳,用单调队列维护。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define ld long double
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=1000100;
const ld eps=1e-5;
const int inf=2147483647;

int n;
ll Arr[maxN];
ll Queue[maxN];
ll F[maxN];

ld Slope(int i,int j);

int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for (int i=1;i<=n;i++) cin>>Arr[i];
    int l=1,r=1;
    Queue[1]=0;
    for (int i=1;i<=n;i++)
    {
        while ((l<r)&&(Slope(Queue[l],Queue[l+1])<2.0*i+eps)) l++;
        F[i]=Arr[i]+F[Queue[l]]+(i-Queue[l]-1)*(i-Queue[l])/2;
        while ((l<r)&&(Slope(Queue[r-1],Queue[r])+eps>Slope(Queue[r],i))) r--;
        Queue[++r]=i;
    }
    cout<<F[n]<<endl;
    return 0;
}

ld Slope(int i,int j)
{
    return (ld)((2.0*F[i]+1.0*i*i+1.0*i)-(2.0*F[j]+1.0*j*j+1.0*j))/(ld)(1.0*i-1.0*j);
}

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ3156]防御准备(动态规划,斜率优化)


HNCJ OIer 一枚