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

Description

Input

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

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

Output

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

Sample Input

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
#include
#include
#include
#include
using namespace std;
int read()
{int x=0,f=1; char ch=getchar();while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();}while (ch>='0' && ch<='9') {x=x*10+ch-'0'; 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)1<<60;for (int i=n; i>=1; i--) A[i]=read();for (int i=1; i<=n; i++) sumid[i]=sumid[i-1]+i;dp[1]=A[1]; que[1]=1; l=r=1;for (int tmp,i=2; i<=n; i++){while (l1]);tmp=que[l];dp[i]=dp[tmp]+sumid[i-1]-sumid[tmp]-(i-tmp-1)*tmp+A[i];while (l1],que[r])) r--;que[++r]=i;}for (int i=1; i<=n; i++) ans=min(ans,dp[i]+sumid[n]-sumid[i]-(long long)(n-i)*i);printf("%lld\n",ans);return 0;
}

上文所述WA成狗...MDZZ

转载于:https://www.cnblogs.com/DaD3zZ-Beyonder/p/5388392.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！