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.