描述
地精工程师的主要工作就是埋炸弹…… 在一个M*N的矩形土地上，会有许多的小兵侵入，这些小兵都是钱啊，地精工程师怎能放弃这个刷钱的机会？于是，地精工程师决定埋一个遥控炸弹，等小兵都站好再引爆。 地精工程师的炸弹可以轰掉一个矩形区域，并收到所有这个矩形区域中小兵的钱。 有的小兵是魔法师……炸掉这个小兵可以让得到的钱乘2，如果炸掉多个这样的小兵，得到的钱就是原来的2^x倍（x为炸掉魔法师的个数） 地精工程师想知道，他最多能得到多少钱？
输入
第一行，两个数M，N 接下来M行N列的矩阵，表示炸掉每个位置上的小兵的钱 接下来一个数T 接下来T行，每行两个数x，y，表示位于x，y的小兵是魔法师
输出
一个数，表示最多得到多少钱
样例输入
样例输出
6
提示
M，N<=100 T<=10 矩阵中的数在[-500，500]之间
【Solution】
这是一个最优子矩阵的变形，其中的矩阵价值是可变的，所以我们需要在原来的方程上多加一维。
(Zip后)F[i,j]表示前i个数中已经选了j个魔法兵所获得的最大金钱。B[i]存储每个格子的魔法兵数目。
F[i,j]←max{((F[i-1,j-b[i]]/2j-b[i])+a[i])*2j,a[i]*2b[i]}
不好意思，我的程序只能通过45%的测试点，其他都WA了…等要来数据再调吧…让人纠结啊。
【Code】
1: Program GoblinTech(input,output);
2: var F:array[0..100,-10..10]of int64;
3: a:array[1..100,1..100]of longint;
4: Magic:array[1..100,1..100]of boolean;
5: aa,b,bb:array[0..100]of longint;
6: up,down,i,t,j,n,m,x,y:longint;
7: ans:int64;
8: Function max(a,b:Longint):longint;
9: begin
10: if a>b then exit(a) else exit(b);
11: end;
12: Procedure zip(up,down:longint);
13: var i,j:longint;
14: begin
15: fillchar(aa,sizeof(aa),0);
16: fillchar(b,sizeof(b),0);
17: for i:=1 to m do
18: begin
19: bb[i]:=bb[i-1];
20: for j:=up to down do
21: begin
22: inc(aa[i],a[j,i]);
23: if Magic[j,i] then begin inc(b[i]);inc(bb[i]);end;
24: end;
25: end;
26: end;
27: begin
28: readln(n,m);
29: for i:=1 to n do
30: for j:=1 to m do
31: read(a[i,j]);
32: readln(t);fillchar(Magic,sizeof(Magic),false);
33: for i:=1 to t do begin readln(x,y);Magic[x,y]:=true;end;
34: ans:=-5120000000;
35: for up:=1 to n do
36: for down:=1 to n do
37: begin
38: Zip(up,down);
39: fillchar(F,sizeof(F),0);
40: for i:=1 to m do
41: for j:=b[i] to bb[i] do
42: begin
43: F[i,j]:=max(((F[i-1,j-b[i]] div (1<<(j-b[i])))+aa[i])*(1<
44: aa[i]*(1<
45: if F[i,j]>ans then ans:=F[i,j];
46: end;
47: end;
48: writeln(ans);
49: end.