我们不妨将所有权值打到一棵树上，这很容易想到。
考虑暴力，如果我们选择了 \(w\) 个点，修改后我们会从叶子节点依次合并去计算贡献。
很显然我们可以动态规划维护。
\(f[p][w][0/1/2]\) 表示选了 \(w\) 个点，后整个区间的状态为 \(0/1/2\) 。
0和1表示整个区间全为这个数。2表示混合区间，但也包含前两个状态。
特殊的，进行合并时，注意左右区间可以合并时，减去合并贡献。
注意每个节点都有贡献。
至此，此题得解。
具体复杂度 \(\mathcal{O}(2^k w^2)\) 。
这道题少有人做，但是希望对您有用，谢谢。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const int N = 500;
const int M = 80;
const int Mod = 1e9 + 7;
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
int n, w;
char s[N];
int c[N];
int f[N][M][3];
// 0 1 01
int ls(int p) { return p << 1; }
int rs(int p) { return p << 1 | 1; }
void dfs(int p, int l, int r)
{
if (l == r)
{
if (s[l] == '1')
{
f[p][0][1] = 1;
f[p][0][2] = 1;
}
else
{
f[p][0][0] = 1;
f[p][1][1] = c[l] + 1;
f[p][0][2] = 1;
f[p][1][2] = c[l] + 1;
}
return;
}
int mid = l + r >> 1;
dfs(ls(p), l, mid);
dfs(rs(p), mid + 1, r);
for (int i = 0; i <= w; ++i)
{
for (int j = 0; j <= i; ++j)
{
for (int u = 0; u <= 2; ++u)
{
for (int v = 0; v <= 2; ++v)
{
f[p][i][2] = min(f[p][i][2], f[ls(p)][j][u] + f[rs(p)][i - j][v] + 1);
}
}
f[p][i][0] = min(f[p][i][0], f[ls(p)][j][0] + f[rs(p)][i - j][0] - 2 + 1);
f[p][i][1] = min(f[p][i][1], f[ls(p)][j][1] + f[rs(p)][i - j][1] - 2 + 1);
f[p][i][2] = min(f[p][i][2], min(f[p][i][0], f[p][i][1]));
}
}
}
int main()
{
memset(f, Mod, sizeof(f));
n = read(), w = read();
scanf("%s", s + 1);
n = 1 << n;
for (int i = 1; i <= n; ++i)
{
c[i] = read();
if (s[i] == '1')
c[i] = 0;
}
dfs(1, 1, n);
printf("%d\n", min(min(f[1][w][0], f[1][w][1]), f[1][w][2]));
return 0;
}