第一眼DP，发现不可做，第二眼就只能$O(2^{1024})$暴搜了。
重新审视一下这个DP，f[x][i]表示在x的祖先已经全部染色之后，x的子树中共有i个参战平民的最大贡献。
设k为总结点数，对于DFS，我们有$T(1)=O(log k)$，$T(k)=4T(frac{k}{2})+O(k^2)$。
根据主定理，$O(n^{log_ba})=O(n^2)$。故时间复杂度为$O(k^2log k)$，即$O(2^{2n}n)$。
1 #include<cstdio> 2 #include<algorithm> 3 #define rep(i,l,r) for (int i=(l); i<=(r); i++) 4 using namespace std; 5 6 const int N=2010; 7 int n,m,mx,c[N],a[2][N][N],f[N][N]; 8 9 void dfs(int x,int d){ 10 if (d==n){ 11 f[x][0]=f[x][1]=0; 12 for (int j=x>>1; j; j>>=1) f[x][c[j]]+=a[c[j]][x][j]; 13 return; 14 } 15 int ls=x<<1,rs=ls|1; 16 rep(i,0,1<<(n-d)) f[x][i]=0; 17 c[x]=0; dfs(ls,d+1); dfs(rs,d+1); 18 rep(i,0,min(m,1<<(n-d))) rep(j,0,min(m-i,(1<<(n-d))-i)) 19 f[x][i+j]=max(f[x][i+j],f[ls][i]+f[rs][j]); 20 c[x]=1; dfs(ls,d+1); dfs(rs,d+1); 21 rep(i,0,min(m,1<<(n-d))) rep(j,0,min(m-i,(1<<(n-d))-i)) 22 f[x][i+j]=max(f[x][i+j],f[ls][i]+f[rs][j]); 23 } 24 25 int main(){ 26 freopen("bzoj4007.in","r",stdin); 27 freopen("bzoj4007.out","w",stdout); 28 scanf("%d%d",&n,&m); 29 rep(i,1<<(n-1),(1<<n)-1) 30 for (int j=i>>1; j; j>>=1) scanf("%d",&a[1][i][j]); 31 rep(i,1<<(n-1),(1<<n)-1) 32 for (int j=i>>1; j; j>>=1) scanf("%d",&a[0][i][j]); 33 dfs(1,1); 34 rep(i,0,m) mx=max(mx,f[1][i]); 35 printf("%d ",mx); 36 return 0; 37 }