某岛

… : "…アッカリ～ン . .. . " .. .
September 19, 2021

暴力枚举 O(n3)

const int M = int(3e2) + 9;
const int N = int(3e2) + 9;
int dp[N][M], cost[N], value[N]; VI adj[N];
int n, m;

void dfs(int u = 0) {
FLC(dp[u], 0x80);
DWN_1(i, m, cost[u]) dp[u][i] = value[u];

dfs(v);
DWN_1(i, m, cost[u]) {
FOR_1(j, cost[u], i) {
checkMax(dp[u][i], dp[u][j] + dp[v][i-j]);
}
}
}
}

int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif
RD(n, m);
REP_1(i, n) {
int p; RD(p, value[i]); cost[i] = 1;
}
dfs();
cout << dp[0][m] << endl;
}

状态继承 O(n2)

const int N = int(1e5) + 9;
const int M = int(1e5) + 9;
int n, m;

void dfs(int u, int m, VI& dpu) {
m -= cost[u];
VI dpv = dpu; dfs(v, m, dpv);
FOR_1(i, 0, m) checkMax(dpu[i], dpv[i]);
}
m += cost[u];
DWN_1(i, m, cost[u]) dpu[i] = dpu[i-cost[u]] + value[u];
REP(i, cost[u]) dpu[i] = -INF;
}

int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif
RD(n, m);
REP_1(i, n) {
int p; RD(p, value[i]); cost[i] = 1;
}
VI dp0; dp0.resize(m+1);
dfs(0, m, dp0);
cout << dp0[m] << endl;
}

P1273 有线电视网
https://www.luogu.com.cn/problem/P1273

const int N = (3e3) + 9;
int dp[N][N], bonus[N];
int n, m, z;

bool isLeaf(int u) {
return u > n-m;
}

void dfs0(int u) {
sz[u] = isLeaf(u);
int v = e.fi;
dfs0(v);
sz[u] += sz[v];
}
}

void dfs(int u) {
FLC(dp[u], 0x80);
dp[u][0] = 0;

if (isLeaf(u)) {
dp[u][1] = bonus[u];
return;
}

int v = e.fi, w = e.se;
dfs(v);
DWN_1(i, sz[u], 1) {
REP_1(j, sz[v]) {
checkMax(dp[u][i], dp[u][i-j] + dp[v][j] - w);
}
}
}
}

int main(){
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif
RD(n, m); REP_1(u, n-m) {
Rush {
int v, c; RD(v, c);
}
}

FOR_1(u, n-m+1, n) RD(bonus[u]);

dfs0(1); dfs(1);
DWN_1(i, m, 0) {
if (dp[1][i] >= 0) {
cout << i << endl;
return 0;
}
}
}

道路重建

const int N = (1e5) + 9;
int n, m, z;

VI dp[N];
// dp[u][i]，保留 u 节点同时子树再保留 i 个节点的子树，最少删多少边

void dfs(int u, int p){

sz[u] = 1; dp[u].PB(0);

for (auto v: adj[u]) if (v != p) {
dfs(v, u);

REP(i, SZ(dp[u])) dp[u][i] += 1;
DO(min(sz[v], m+1-sz[u])) dp[u].PB(INF);
sz[u] += sz[v];

DWN(i, SZ(dp[u]), 1) {
REP(j, min(SZ(dp[v]), i)) {
checkMin(dp[u][i], dp[u][i-1-j] + dp[v][j] - 1);
}
}
}

if (sz[u] > m) checkMin(z, dp[u][m] + bool(p));
}

signed main(){
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif
RD(n, m); --m; DO(n-1){
int a, b; RD(a, b);