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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

【DP】特别行动队  

2014-04-29 10:21:53|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
@特别行动队
让我想到了空手撕鬼子……
斜率优化的DP,和玩具装箱那个题几乎一模一样啊……
【DP】特别行动队 - 时光机 - 时光机TimeMachine
第一次Wa是因为longlong的除法导致精度损失问题
第二次是忘记吧I64d改成lld不要在意……
调了好长时间,果然我很弱


/*

f[i] = a*(sum[i] - sum[j-1])^2 + b*(sum[i] - sum[j-1]) + c + f[j-1]

k<j
jc[k] < jc[j]

a*(sum[i] - sum[j-1])^2 + b*(sum[i] - sum[j-1]) + c + f[j-1] >= a*(sum[i] - sum[k-1])^2 + b*(sum[i] - sum[k-1]) + c + f[k-1]

a*sum[i]^2 - 2*a*sum[i]*sum[j-1]+a*sum[j-1]^2 + b*sum[i] - b*sum[j-1] + c + f[j-1] >= a*sum[i]^2 - 2*a*sum[i]*sum[k-1] + a*sum[k-1]^2 + b*sum[i] - b*sum[k-1] + c + f[k-1]

- 2*a*sum[i]*sum[j-1]+a*sum[j-1]^2 - b*sum[j-1] + f[j-1] >= - 2*a*sum[i]*sum[k-1] + a*sum[k-1]^2 - b*sum[k-1] + f[k-1]

- 2*a*sum[i]*(sum[j-1] - sum[k-1]) >= ( ( a*sum[k-1]^2 - b*sum[k-1] + f[k-1] ) - ( a*sum[j-1]^2 - b*sum[j-1] + f[j-1] ) )

- 2*a*sum[i] >= ( ( a*sum[k-1]^2 - b*sum[k-1] + f[k-1] ) - ( a*sum[j-1]^2 - b*sum[j-1] + f[j-1] ) ) / (sum[j-1] - sum[k-1])

a<0 -> -2*a>0
x[i] > 0
when i++ -> sum[i]++
ok

Dx(j) = sum[j-1]
Dy(j) = a*sum[j-1]^2 - b*sum[j-1] + f[j-1]


*/
#include <cstdio>
#include <cmath>
#include <queue>
using namespace std;
typedef long long LL;
const int N = 1000000+1;
const LL _MAX = 100000000000000000LL;
int n,m,data[N],jc[N];
LL sum[N],f[N],A,B,C;
LL pow2(LL a){return a*a;}
struct Point{
LL x,y;int i;
Point(){}
Point(int j){
y=pow2(sum[j-1])*A - B*sum[j-1] + f[j-1];
x=sum[j-1];i=j;
}
};
short better(Point a,Point b,int i){
if(b.x==a.x) return 0>=a.y-b.y;
else return -2*A*sum[i]*(b.x-a.x) >= (a.y-b.y);
}
deque<Point> dui;
LL get(int i,int j){return A*pow2(sum[i] - sum[j-1]) + B*(sum[i] - sum[j-1]) + C + f[j-1];}
short cmp(Point a,Point b,Point c){ return (a.y-b.y)*(c.x-b.x) >= (b.y-c.y)*(b.x-a.x);}
LL scan(){
char cc=' ';LL fh=1;LL re=0;
while(cc==' '||cc=='\n'||cc=='\r') cc=getchar();
if(cc=='-'){fh=-1;cc=getchar();}
if(cc=='+'){fh=1;cc=getchar();}
while('0'<=cc&&cc<='9'){
re=re*10+cc-'0';
cc=getchar();
}return re*fh;
}
void print(){
int i,j=dui.size();
for(i=0;i<j;i++)
printf("%d ",dui[i].i);
printf("\n");
for(i=0;i<j;i++)
printf("%d ",dui[i].y);
printf("\n");
}
int main(){
int i,j,s;
freopen("input.txt","r",stdin);
n=scan();A=scan();B=scan();C=scan();
for(i=1;i<=n;i++){
data[i]=scan();
sum[i]=sum[i-1]+data[i];
}
dui.push_front(Point(1));
for(i=1;i<=n;i++) f[i]=-_MAX;
for(i=1;i<=n;i++){
while(dui.size()>1&& better(dui[0],dui[1],i) )
dui.pop_front();
Point a=dui[0];
//printf("[%d] \n",i);print();
jc[i]=a.i;
f[i]=get(i,a.i);
a=Point(i+1);
//(s=dui.size())>1 不要写成 s=dui.size()>1
while((s=dui.size())>1&& cmp(dui[s-2],dui[s-1],a) ) dui.pop_back();
dui.push_back(a);
//printf("[%d] \n",i);print();
}
/*
for(i=1;i<=n;i++)
printf("%d ",jc[i]);
printf("\n");
*/
printf("%lld",f[n]);
return 0;
}


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

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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