注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ1911][Apio2010]特别行动队  

2014-12-01 20:04:49|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1911: [Apio2010]特别行动队

Time Limit: 4 Sec  Memory Limit: 64 MB
Submit: 2380  Solved: 1037
[Submit][Status]

Description

[BZOJ1911][Apio2010]特别行动队 - Trinkle - n+e

Input

[BZOJ1911][Apio2010]特别行动队 - Trinkle - n+e

Output

[BZOJ1911][Apio2010]特别行动队 - Trinkle - n+e

Sample Input

4
-1 10 -20
2 2 3 4

Sample Output

9

HINT

[BZOJ1911][Apio2010]特别行动队 - Trinkle - n+e

Solution

f[i]=max(f[j]+A*(sum[i]-sum[j])^2+B*(sum[i]-sum[j])+C)

斜率优化套一套

两个不等号调一调

23333

现在的斜率优化,既不要推式子,又不要考虑符号了,真无脑= =

Code

/**************************************************************
    Problem: 1911
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:648 ms
    Memory:28148 kb
****************************************************************/
 
#include<cstdio>
#define N 1000010
int aa,n,l,r,i,j,q[N];long long a,b,c,sum[N],y[N],xx,f[N];char ch;int F(){
    while(ch=getchar(),ch<'0'||ch>'9');aa=ch-'0';
    while(ch=getchar(),ch>='0'&&ch<='9')aa=aa*10+ch-'0';return aa;
}
int main(){
    scanf("%d%lld%lld%lld",&n,&a,&b,&c);
    for(i=1;i<=n;q[++r]=i++){
        sum[i]=sum[i-1]+F(),xx=2*a*sum[i];
        while(l<r&&y[q[l+1]]-y[q[l]]>=xx*(sum[q[l+1]]-sum[q[l]]))l++;
        xx=sum[i]-sum[q[l]],f[i]=f[q[l]]+a*xx*xx+b*xx+c,y[i]=f[i]+(a*sum[i]-b)*sum[i];
        while(l<r&&(y[q[r]]-y[q[r-1]])*(sum[i]-sum[q[r]])<=(y[i]-y[q[r]])*(sum[q[r]]-sum[q[r-1]]))r--;
    }
    printf("%lld\n",f[n]);
}

  评论这张
 
阅读(26)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018