根本想不出来。。。
原来还是暴力出奇迹啊QAQ
无限ymymym中
/**************************************************************
Problem: 4007
User: rausen
Language: C++
Result: Accepted
Time:240 ms
Memory:13216 kb
****************************************************************/ #include <cstdio>
#include <cstring>
#include <algorithm> using namespace std;
const int N = ( << ) + ; int n, m, ans;
int a[N][N], b[N][N], f[N][N];
int now[N]; inline int read(); #define ls p << 1
#define rs p << 1 | 1
void dfs(int p, int sz) {
int i, j, mnl, mxl, tot;
if (sz == ) {
f[p][] = f[p][] = ;
for (i = p >> ; i; i >>= )
if (now[i] == ) f[p][] += a[p][i];
else f[p][] += b[p][i];
return;
}
tot = min(sz, m);
memset(f[p], , sizeof(f[][]) * (tot + ));
now[p] = ;
dfs(ls, sz >> ), dfs(rs, sz >> );
for (i = ; i <= tot; ++i) {
mnl = max(i - (sz >> ), ), mxl = min(sz >> , i);
for (j = mnl; j <= mxl; ++j)
f[p][i] = max(f[p][i], f[ls][j] + f[rs][i - j]);
} now[p] = ;
dfs(ls, sz >> ), dfs(rs, sz >> );
for (i = ; i <= tot; ++i) {
mnl = max(i - (sz >> ), ), mxl = min(sz >> , i);
for (j = mnl; j <= mxl; ++j)
f[p][i] = max(f[p][i], f[ls][j] + f[rs][i - j]);
}
}
#undef ls
#undef rs int main() {
int i, j;
n = read(), m = read();
for (i = << n - ; i < << n; ++i)
for (j = i >> ; j; j >>= )
a[i][j] = read();
for (i = << n - ; i < << n; ++i)
for (j = i >> ; j; j >>= )
b[i][j] = read();
dfs(, << n - );
for (ans = i = ; i <= m; ++i)
ans = max(ans, f[][i]);
printf("%d\n", ans);
return ;
} inline int read() {
static int x;
static char ch;
x = , ch = getchar();
while (ch < '' || '' < ch)
ch = getchar();
while ('' <= ch && ch <= '') {
x = x * + ch - '';
ch = getchar();
}
return x;
}