社区讨论
时间复杂度n的4次方能16分吗?
P14637[NOIP2025] 树的价值参与者 6已保存回复 10
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 9 条
- 当前快照
- 1 份
- 快照标识符
- @milsnyh0
- 此快照首次捕获于
- 2025/11/30 22:07 3 个月前
- 此快照最后确认于
- 2025/12/03 17:05 3 个月前
rt
加了点剪枝,但是没有认真卡常。
CPP加了点剪枝,但是没有认真卡常。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define GL return
#define HF 0
const int N = 20, M = (1 << 13) + 20;
int test, n, m, fa[N], f[N][M], tmp[M];
vector<int> edges[N];
int mex (int x) {
for (int i = 0; i < n; i++) {
if (x >> i & 1) {
} else {
return i;
}
}
return n;
}
inline void dfs (const int &x) {
for (int i = 0; i < n; i++) {
if (i == 0) {
f[x][1 << i] = 1;
} else {
f[x][1 << i] = 0;
}
}
for (auto y : edges[x]) {
dfs(y);
for (int i = 0; i < 1 << n; i++) {
tmp[i] = -64000;
}
for (int i = 0; i < 1 << n; i++) {
if (f[x][i] >= 0) {
for (int j = 0; j < 1 << n; j++) {
if (f[y][j] >= 0) {
tmp[i | j] = max(tmp[i | j], f[x][i] + f[y][j] - mex(i) + mex(i | j));
}
}
}
}
for (int i = 0; i < 1 << n; i++) {
f[x][i] = tmp[i];
}
}
}
inline void solve () {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
edges[i].clear();
for (int j = 0; j < 1 << n; j++) {
f[i][j] = -64000;
}
}
for (int i = 2; i <= n; i++) {
scanf("%d", &fa[i]);
edges[fa[i]].push_back(i);
}
dfs(1);
ll ans = -64000;
for (int i = 0; i < 1 << n; i++) {
ans = max(ans, 1ll * f[1][i]);
}
printf("%lld\n", ans);
GL;
}
int main() {
for (scanf("%d", &test); test--; solve());
GL HF;
}
回复
共 10 条回复,欢迎继续交流。
正在加载回复...