BZOJ

BZOJ 4007

传送门

头一次见正解是DFS的题…

普通的搜索是枚举最下边一层的状态然后从下往上算

正解是从上往下枚举每个人是当军官还是管后勤，回溯时拿个树形DP来更新答案

这样大概减少了好多重复的计算吧…

设$F_{i,j}$为$i$的子树中选$j$个当兵的最大收益，然后直接算即可


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
program bzoj_4007;
var warrior,farmer:array[1..512,1..9]of longint;
    f:array[1..1024,0..1024]of longint;
    officer:array[1..512]of boolean;
    n,m,i,j,ans:longint;
 
function min(a,b:longint):longint;
begin
  if a<b then exit(a) else exit(b);
end;
 
function max(a,b:longint):longint;
begin
  if a>b then exit(a) else exit(b);
end;
 
procedure dfs(t,size:longint);
var i,j,cnt:longint;
begin
  if t>=1<<(n-1) then
  begin
    i:=1;
    f[t,0]:=0;
    f[t,1]:=0;
    while t>>i>0 do
    begin
      if officer[t>>i] then inc(f[t,1],warrior[t-1<<(n-1)+1,i]) else inc(f[t,0],farmer[t-1<<(n-1)+1,i]);
      inc(i);
    end;
    exit;
  end;
  cnt:=min(size,m);
  for i:=0 to cnt do f[t,i]:=0;
  officer[t]:=false;
  dfs(t<<1,size>>1);
  dfs(t<<1+1,size>>1);
  for i:=0 to cnt do
  for j:=max(i-size>>1,0) to min(i,size>>1) do f[t,i]:=max(f[t,i],f[t<<1,j]+f[t<<1+1,i-j]);
  officer[t]:=true;
  dfs(t<<1,size>>1);
  dfs(t<<1+1,size>>1);
  for i:=0 to cnt do
  for j:=max(i-size>>1,0) to min(i,size>>1) do f[t,i]:=max(f[t,i],f[t<<1,j]+f[t<<1+1,i-j]);
end;
 
begin
  readln(n,m);
  for i:=1 to 1<<(n-1) do
  for j:=1 to n-1 do read(warrior[i,j]);
  for i:=1 to 1<<(n-1) do
  for j:=1 to n-1 do read(farmer[i,j]);
  dfs(1,1<<(n-1));
  ans:=0;
  for i:=0 to m do ans:=max(ans,f[1,i]);
  writeln(ans);
end.