APIO2010特别行动队（单调队列、斜率优化）

2020-12-13 02:33

阅读：639

标签：c style class blog code a

其实这题一看知道应该是DP，再一看数据范围肯定就是单调队列了。

不过我还不太懂神马单调队列、斜率优化……

附上天牛的题解：http://www.cnblogs.com/neverforget/archive/2012/04/19/2456483.html

 1 var f,g:array[0..1000050] of int64;
 2     s,q:array[0..1000050] of longint;
 3     a,b,c,n,i,h,t,x:longint;
 4     bestk:double;
 5 procedure init;
 6  begin
 7  readln(n);
 8  readln(a,b,c);
 9  s[0]:=0;
10  for i:=1 to n do
11   begin
12   read(x);
13   s[i]:=s[i-1]+x;
14   end;
15  end;
16 function k(x,y:longint):double;
17  begin
18  exit(double(g[y]-g[x])/(s[y]-s[x]));
19  end;
20 procedure main;
21  begin
22  f[0]:=0;h:=1;t:=1;q[1]:=0;
23  for i:=1 to n do
24   begin
25   bestk:=double(2*a*s[i]);
26   while (hand (k(q[h],q[h+1])>=bestk) do inc(h);
27   f[i]:=int64(f[q[h]])+int64(a)*int64(s[i]-s[q[h]])*int64(s[i]-s[q[h]])
28        +int64(b)*int64(s[i]-s[q[h]])+int64(c);
29   g[i]:=int64(f[i])+int64(a)*int64(s[i])*int64(s[i])-int64(b)*int64(s[i]);
30   while (h+1and (k(q[t],i)>k(q[t-1],q[t])) do dec(t);
31   inc(t);
32   q[t]:=i;
33   end;
34  end;
35 procedure print;
36  begin
37  writeln(f[n]);
38  end;
39 begin
40  init;
41  main;
42  print;
43 end.

View Code

APIO2010特别行动队（单调队列、斜率优化）,搜素材,soscw.com

APIO2010特别行动队（单调队列、斜率优化）

标签：c style class blog code a

原文地址：http://www.cnblogs.com/zyfzyf/p/3773965.html

上一篇：Springboot + Freemarker（一）

下一篇：CSS 类名的单词连字符：下划线还是连接符？

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：APIO2010特别行动队（单调队列、斜率优化）
文章链接：http://soscw.com/essay/25834.html

亲，登录后才可以留言！

APIO2010特别行动队（单调队列、斜率优化）

评论

热门文章

推荐文章

最新文章

置顶文章