习题：进攻策略（背包+二分+队列）

时间：2016-03-20 19:25:34 收藏：0 阅读：424

进攻策略
【题目描述】
植物大战僵尸这款游戏中，还有一个特别的玩儿法：玩家操纵僵尸进攻植物。
首先，僵尸有m种（每种僵尸都是无限多的），玩家可以选择合适的僵尸来进攻。使用第i种僵尸需要花费Wi资源，可以得到Pi的攻击效果。在这里，我们认为多个僵尸总的攻击效果就是他们每个攻击效果的代数和。
地图共有n行，对于第i行，最左端有若干植物，这些植物需要至少Qi的攻击才能被全部消灭。若一行上的植物全部被消灭，我们称这一行被攻破。
由于资源紧张，你只有总量为K的资源，不一定能够攻破所有行。但统治者希望攻破相邻的T行，并希望T尽量的大。你能帮他算出T的值吗？
【输入数据】
第一行三个非负整数：m、n、K；
第二行m个正整数，第i个数表示Wi；
第三行m个正整数，第i个数表示Pi；
第四行n个非负整数，第i个数表示Qi。
【输出数据】
一个正整数T。
【输入样例】
3 11 39
5 2 11
3 1 7
5 3 6 10 3 2 4 200 1 1 1
【输出样例】
4
（样例说明：打掉10 3 2 4这相邻的4行，需要的最小代价是16+5+4+7=32，不超过39。）
【数据规模】
对于70%的数据：n<=1000
对于100%的数据：n<=200000，m<=100，K<=1000，所有Pi、Qi<=100000000

分析：

70分算法是利用DP算出造成qi伤害的最小花费，再枚举要攻破的区间左右端点，找到最长的即可。但由于qi较大，时间效率不高。

AC算法是利用背包求1..k资源所能造成的最大伤害，显然它们的值为单调不减的，对于每行用二分查找找到最大伤害足以消灭它的资源数且让这个资源最少，就找到了消灭各行的最小花费，然后用队列求出最大的消耗资源<=k的区间。

代码：

program attack;
var
  f:array[0..1000]of int64;
  w,p:array[0..100]of int64;
  a,q,team:array[0..200000]of int64;
  n,i,m,j,h,ans,l,r,mid,k:longint;  sum:int64;
function max(x,y:int64):int64;
begin
  if x>y then max:=x else max:=y;
end;
begin
  assign(input,‘attack.in‘);
  reset(input);
  assign(output,‘attack.out‘);
  rewrite(output);
  readln(m,n,k);
  for i:=1 to m do read(w[i]);readln;
  for i:=1 to m do read(p[i]);readln;
  for i:=1 to n do read(q[i]);
  fillchar(f,sizeof(f),0);
  for i:=1 to m do
   for j:=w[i] to k do
    f[j]:=max(f[j],f[j-w[i]]+p[i]);
  f[k+1]:=maxlongint;
  for i:=1 to n do
    begin
      l:=0; r:=k+1;
      while l<r do
       begin
         mid:=(l+r) div 2;
         if f[mid]>=q[i] then r:=mid
          else l:=mid+1;
       end;
       a[i]:=r;
    end;
   h:=1;
  for i:=1 to n do
   begin
     team[i]:=a[i]; inc(sum,a[i]);
     while (sum>k)and(h<=i) do
      begin
        dec(sum,team[h]); inc(h);
      end;
      ans:=max(ans,i-h+1);
   end;
  writeln(ans);
  close(input); close(output);
end.

View Code

原文：http://www.cnblogs.com/qtyytq/p/5299203.html