az
by wangzl @ 2023-01-23 11:08:35
鹅
by Hell0_W0rld @ 2023-01-23 11:09:04
每 A 就没事
by InversionShadow @ 2023-01-23 11:18:07
每 = 没
by InversionShadow @ 2023-01-23 11:18:41
在 DP 时外层正向枚举可以得 92 分。
```cpp
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 155;
int n, tg, sz[MAXN], f[MAXN][MAXN], ans = 0x3f3f3f3f;
vector<int> to[MAXN];
void solve (int x, int fa) {
sz[x] = 1;
f[x][0] = 0;
for (int p: to[x]) {
if (p == fa) continue;
solve (p, x);
sz[x] += sz[p];
for (int i = 1;i < sz[x];i++) { // 正确写法：for (int i = sz[x] - 1;i >= 1;i--) {
for (int j = 1;j <= min(i, sz[p] - 1);j++) {
f[x][i] = min(f[x][i], f[x][i - j] + f[p][j]);
}
if (i >= sz[p]) f[x][i] = min(f[x][i], f[x][i - sz[p]] + 1);
}
}
if (sz[x] >= tg) ans = min(ans, f[x][sz[x] - tg] + (x != 1));
}
int main () {
memset (f, 0x3f, sizeof(f));
cin >> n >> tg;
int x, y;
for (int i = 1;i < n;i++) {
cin >> x >> y;
to[x].push_back(y);
to[y].push_back(x);
}
solve (1, 0);
cout << ans << endl;
return 0;
}
```
by M1ndeveloped @ 2023-07-20 10:20:18
~~没 A 就没事~~
by Linzijian2012 @ 2023-12-10 21:27:40