搜索+状压+DP。
注意到一个性质：考虑一棵以x为根的子树，在x到原树的根的路径上的点如果都已经确定了方案，那么x的左右儿子的决策就彼此独立，互不影响了。所以我们考虑状压一条路径上每一层节点的状态，求出dp[u][x] : 以u为根的子树中分配x个作战平民的最大收益是多少（注意因为是在dfs当中，所以dp数组存的是在当前状况下的最优解）。
代码挺短的，可食用~
#includeusing namespace std;#define maxn 1025 int n, m, tot, ans, dp[maxn][maxn];int w[maxn][20], f[maxn][20];int read(){ int x = 0, k = 1; char c; c = getchar(); while(c < '0' || c > '9') { if(c == '-') k = -1; c = getchar(); } while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * k;}void dfs(int x, int y, int st, int cnt){ for(int i = 0; i <= cnt; i ++) dp[x][i] = 0; if(y == n - 1) { int id = x - (1 << y); for(int i = 0; i < y; i ++) if(st & (1 << i)) dp[x][1] += w[id][i]; else dp[x][0] += f[id][i]; return; } dfs(x << 1, y + 1, st | (1 << y), cnt >> 1); dfs(x << 1 | 1, y + 1, st | (1 << y), cnt >> 1); for(int i = cnt >> 1; ~i; i --) for(int j = cnt >> 1; ~j; j --) dp[x][i + j] = max(dp[x][i + j], dp[x << 1][i] + dp[x << 1 | 1][j]); dfs(x << 1, y + 1, st, cnt >> 1); dfs(x << 1 | 1, y + 1, st, cnt >> 1); for(int i = cnt >> 1; ~i; i --) for(int j = cnt >> 1; ~j; j --) dp[x][i + j] = max(dp[x][i + j], dp[x << 1][i] + dp[x << 1 | 1][j]);}int main(){ n = read(), m = read(); tot = (1 << (n - 1)); for(int i = 0; i < tot; i ++) for(int j = n - 2; ~j; j --) w[i][j] = read(); for(int i = 0; i < tot; i ++) for(int j = n - 2; ~j; j --) f[i][j] = read(); dfs(1, 0, 0, tot); ans = 0; for(int i = 0; i <= m; i ++) ans = max(ans, dp[1][i]); printf("%d\n", ans); return 0; }