BZOJ1911：[Apio2010]特别行动队——题解

2021-02-16 08:21

阅读：496

http://www.lydsy.com/JudgeOnline/problem.php?id=1911

技术分享图片

又是一个显然的dp……好吧我懒得讲了。

s[i]是战斗力前缀和。

我们仍然设k，化简一下得到f[j]-2*a*s[i]s[j]+a*s[j]^2-b*s[j]>f[k]-2*a*s[i]s[k]+a*s[k]^2-b*s[k]

于是得到：

0.5*(f[j]+a*s[j]*s[j]-b*s[j]-f[k]-a*s[k]*s[k]+b*s[k])/(a*(s[j]-s[k]))

显然可以斜率优化了。

至于剩下的套路部分就请看土地购买这道题的解法吧。

#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int N=1000010;
const ll INF=1e18;
inline int read(){
    int X=0,w=1;char ch=0;
    while(ch‘0‘||ch>‘9‘){if(ch==‘-‘)w=-1;ch=getchar();}
    while(ch>=‘0‘&&ch‘9‘)X=(X1)+(X3)+ch-‘0‘,ch=getchar();
    return X*w;
}
int n,l,r;
ll a,b,c;
ll f[N],q[N],s[N];
inline double suan(int k,int j){
    return 0.5*(f[j]+a*s[j]*s[j]-b*s[j]-f[k]-a*s[k]*s[k]+b*s[k])/(a*(s[j]-s[k]));
}
int main(){
    n=read(),a=read(),b=read(),c=read();
    for(int i=1;i1]+read();
    for(int i=1;i){
        while(l1])double)s[i])l++;
        ll k=s[i]-s[q[l]];
        f[i]=f[q[l]]+a*k*k+b*k+c;
        while(l1],q[r]))r--;
        q[++r]=i;
    }
    printf("%lld\n",f[n]);
    return 0;
}

+++++++++++++++++++++++++++++++++++++++++++

+本文作者：luyouqi233。　　　　　　　　　　　　　　+

+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+

+++++++++++++++++++++++++++++++++++++++++++

上一篇：C# litJson 使用方法

下一篇：delphi xe7的unit代码窗按回车不换行解决办法

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：BZOJ1911：[Apio2010]特别行动队——题解
文章链接：http://soscw.com/index.php/essay/56016.html

亲，登录后才可以留言！

BZOJ1911：[Apio2010]特别行动队——题解

评论

热门文章

推荐文章

最新文章

置顶文章