Poj2018 Best Cow Fences — 二分答案转化为动态规划问题

讲解：

幻影^九天麟日 20:43:53
最后让*1000取整输出，所以从0.0000~2000.0000以0.0001为单位精度，二分规定一个平均值，然后判断这个值能否达到
高羽飞 20:45:23
答案为什么是单调的？
幻影^九天麟日 20:45:37
答案只有一个！就好像看商品猜价格，二分，高了就降，低了就升
高羽飞 20:46:32
你怎么知道你猜的和正确答案哪个大
幻影^九天麟日 20:46:46
所以要判断是否能达到啊，若能达到就往大的接着二分，达不到就缩小接着二分
高羽飞 20:47:05
哦。
幻影^九天麟日 20:47:24
判断方法就是，构造一个新数列，用原数列所有数减去这个平均值得到新数列，这时就成了最大子序和问题，只需要判断最大子序和是否大于等于0

参考程序：

Source Code

Problem: 2018		User: lydliyudong
Memory: 2408K		Time: 344MS
Language: Pascal		Result: Accepted

• Source Code

var
 a,sum:array[0..100000]of longint;
 f:array[0..100000]of double;
 n,m,i,ans:longint;
 l,r,mid:real;
 bool:boolean;

function max(x,y:double):double;
 begin
  if x>y then exit(x) else exit(y);
 end;

begin
 readln(n,m);
 for i:=1 to n do begin read(a[i]); sum[i]:=sum[i-1]+a[i]; end;
 l:=0.0000; r:=2000.0000;
 while r-l>0.0001 do
  begin
   mid:=(l+r)/2;
   for i:=1 to m do f[i]:=f[i-1]+a[i]-mid;
   if f[m]>=0 then begin l:=mid; continue; end;
   bool:=false;
   for i:=m+1 to n do
    begin
     f[i]:=max(f[i-1]+a[i]-mid,sum[i]-sum[i-m]-mid*m);
     if f[i]>=0 then begin bool:=true; break; end;
    end;
   if bool then l:=mid else r:=mid;
  end;
 ans:=trunc(r*1000);
 writeln(ans);
end.