【BZOJ-3156】防御准备 DP + 斜率优化

3156: 防御准备

Time Limit: 10 Sec Memory Limit: 512 MB
Submit: 951 Solved: 446
[Submit][Status][Discuss]

Description

Input

第一行为一个整数N表示战线的总长度。

第二行N个整数，第i个整数表示在位置i放置守卫塔的花费Ai。

Output

共一个整数，表示最小的战线花费值。

Sample Input

10
2 3 1 5 4 5 6 3 1 2

Sample Output

HINT

1<=N<=10^6,1<=Ai<=10^9

Source

Katharon+#1

Solution

斜率优化DP

方案由后面的转移？翻转序列即可..

然后就是转移方程 $dp[i]=min(dp[i],dp[j]+sum[i-1]-sum[j]-(i-j-1)*j+A[i]$

然后斜率优化一下，比较的裸，然后即可

值得注意的地方：

转移的时候，$i=1$提前的处理出来..

在计算答案的时候，注意加long long否则会WA成狗..

Code

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

using namespace std;

int read()

{

    int x=,f=; char ch=getchar();

    while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}

    while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}

    return x*f;

}

#define maxn 1000100

int n,A[maxn]; int que[maxn],l,r;

long long dp[maxn],sumid[maxn],ans;

double slope(long long i,long long j)

{return (double)(dp[i]-dp[j]-sumid[i]+sumid[j]+i-j+i*i-j*j)/(double)(i-j);}

int main()

{

    n=read(); ans=(long long)<<;

    for (int i=n; i>=; i--) A[i]=read();

    for (int i=; i<=n; i++) sumid[i]=sumid[i-]+i;

    dp[]=A[]; que[]=; l=r=;

    for (int tmp,i=; i<=n; i++)

        {

            while (l<r && slope(que[l],que[l+])<i) l++;

            tmp=que[l];

            dp[i]=dp[tmp]+sumid[i-]-sumid[tmp]-(i-tmp-)*tmp+A[i];

            while (l<r && slope(que[r],i)<slope(que[r-],que[r])) r--;

            que[++r]=i;

        }

    for (int i=; i<=n; i++) ans=min(ans,dp[i]+sumid[n]-sumid[i]-(long long)(n-i)*i);

    printf("%lld\n",ans);

    return ;

}

上文所述WA成狗...MDZZ

秒客网