【暴力DP】[Dota1004]受折磨的灵魂(TormentedSoul)

描述

受折磨的灵魂是一个法系输出型英雄~他的技能全都是AOE（即攻击群体的技能）
在一个N*M的矩阵中，有N*M个敌人……魂之挽歌派受折磨的灵魂去消灭他们
对于每一个敌人（i，j），如果消灭它，魂之挽歌会给受折磨的灵魂a[i,j]的奖赏。
受折磨的灵魂每次可以消灭一个子矩阵中的敌人，但任意两次攻击的矩阵不能重叠。
由于受折磨的灵魂法力有限，他最多只能攻击K次。
受折磨的灵魂想知道，他最多能得到多少奖赏？

输入

第一行，三个数N，M，K
接下来N行，每行M个数，表示每个a[i,j]

输出

一个数，即受折磨的灵魂最多能得到多少奖赏

样例输入

3 2 2
1 -3
2 3
-2 3

样例输出

9

提示

1<=N<=30
1<=M<=3
1<=K<=10

【Solution】

暴力死了…..原来M是1或2（原题SCOI2005最大子矩阵），现在加强到了3……直接代码吧，原理超简单….

【Code】

  1: Program TormentedSoul(input,output);
  2:   var a:array[1..100,1..3]of longint;
  3:       F1:array[0..100,0..10]of longint;
  4:       F2:array[0..10,0..100,0..100]of longint;
  5:       F3:array[0..10,0..50,0..50,0..50]of longint;
  6:       s:array[0..100,1..3]of longint;
  7:       i,j,m,n,k,t,l,p,ans:longint;
  8:   function max(a,b,c:longint):longint;
  9:     begin max:=a;if b>max then max:=b;if c>max then max:=c;end;
 10:   Procedure Solve1;
 11:     begin
 12:       for i:=1 to t do
 13:         for j:=1 to n do
 14:           F1[j,i]:=-19940805;
 15:       for i:=1 to n do
 16:         begin
 17:           readln(a[i,1]);
 18:           s[i,1]:=s[i-1,1]+a[i,1];
 19:         end;
 20:       for i:=1 to n do
 21:         begin
 22:           for k:=1 to t do
 23:             for j:=i-1 downto 0 do
 24:               F1[i,k]:=max(F1[i,k],F1[j,k],F1[j,k-1]+s[i,1]-s[j,1]);
 25:           if F1[i,t]>ans then ans:=F1[i,t];
 26:         end;
 27:       writeln(ans);
 28:     end;
 29:   Procedure Solve2;
 30:     begin
 31:       for i:=1 to t do
 32:         for j:=1 to n do
 33:           for k:=1 to n do
 34:             F2[i,j,k]:=-19940805;
 35:         for i:=1 to n do
 36:           begin
 37:             readln(a[i,1],a[i,2]);
 38:             s[i,1]:=s[i-1,1]+a[i,1];
 39:             s[i,2]:=s[i-1,2]+a[i,2];
 40:           end;
 41:         for j:=1 to n do
 42:           for k:=1 to n do
 43:             begin
 44:               for i:=1 to t do
 45:                 begin
 46:                   for l:=j-1 downto 0 do
 47:                     F2[i,j,k]:=max(F2[i-1,l,k]+s[j,1]-s[l,1],
 48:                                    F2[i,j,k],
 49:                                    F2[i,l,k]);
 50:                   for l:=k-1 downto 0 do
 51:                     F2[i,j,k]:=max(F2[i-1,j,l]+s[k,2]-s[l,2],
 52:                                    F2[i,j,k],
 53:                                    F2[i,j,l]);
 54:                   if k=j then
 55:                     for l:=k-1 downto i-1 do
 56:                       F2[i,j,k]:=max(F2[i,j,k],
 57:                                      F2[i-1,l,l]+s[k,2]-s[l,2]+s[j,1]-s[l,1],
 58:                                      F2[i,l,l]);
 59:             end;
 60:             if F2[t,j,k]>ans then ans:=F2[t,j,k];
 61:           end;
 62:         writeln(ans);
 63:     end;
 64:   Procedure Solve3;
 65:     begin
 66:       for i:=1 to t do
 67:         for j:=1 to n do
 68:           for k:=1 to n do
 69:             for p:=1 to n do
 70:               F3[i,j,k,p]:=-19940805;
 71:       for i:=1 to n do
 72:         begin
 73:           readln(a[i,1],a[i,2],a[i,3]);
 74:           for j:=1 to 3 do s[i,j]:=s[i-1,j]+a[i,j];
 75:         end;
 76:       for j:=1 to n do
 77:         for k:=1 to n do
 78:           for p:=1 to n do
 79:             begin
 80:               for i:=1 to t do
 81:                 begin
 82:                   for l:=j-1 downto 0 do
 83:                     F3[i,j,k,p]:=max(F3[i,j,k,p],
 84:                                      F3[i-1,l,k,p]+s[j,1]-s[l,1],
 85:                                      F3[i,l,k,p]);
 86:                   for l:=k-1 downto 0 do
 87:                     F3[i,j,k,p]:=max(F3[i,j,k,p],
 88:                                      F3[i,j,l,p],
 89:                                      F3[i-1,j,l,p]+s[k,2]-s[l,2]);
 90:                   for l:=p-1 downto 0 do
 91:                     F3[i,j,k,p]:=max(F3[i,j,k,p],
 92:                                      F3[i,j,k,l],
 93:                                      F3[i-1,j,k,l]+s[p,3]-s[l,3]);
 94:                  if k=j then
 95:                    for l:=k-1 downto 0 do
 96:                      F3[i,j,k,p]:=max(F3[i,j,k,p],
 97:                                       F3[i,l,l,p],
 98:                                       F3[i-1,l,l,p]+s[j,1]-s[l,1]+s[k,2]-s[l,2]);
 99:                  if j=p then
100:                    for l:=j-1 downto 0 do
101:                      F3[i,j,k,p]:=max(F3[i,j,k,p],
102:                                       F3[i,l,k,l],
103:                                       F3[i-1,l,k,l]+s[j,1]-s[l,1]+s[p,3]-s[l,3]);
104:                  if k=p then
105:                    for l:=k-1 downto 0 do
106:                      F3[i,j,k,p]:=max(F3[i,j,k,p],
107:                                       F3[i,j,l,l],
108:                                       F3[i-1,j,l,l]+s[k,2]-s[l,2]+s[p,3]-s[l,3]);
109:                  if(k=j)and(k=p)then
110:                    for l:=j-1 downto 0 do
111:                      F3[i,j,k,p]:=max(F3[i,j,k,p],
112:                                       F3[i,l,l,l],
113:                                       F3[i-1,l,l,l]+s[j,1]-s[l,1]+s[k,2]-s[l,2]+s[p,3]-s[l,3]);
114:                 end;
115:               if F3[t,j,k,p]>ans then ans:=F3[t,j,k,p];
116:             end;
117:       writeln(ans);
118:     end;
119:   begin
120:     readln(n,m,t);ans:=-19940805;
121:     if m=1 then Solve1;
122:     if m=2 then Solve2;
123:     if m=3 then Solve3;
124:   end.