1 条题解
-
0陈烨鑫 (chenyexin) LV 10 @ 2023-4-25 19:41:17
# include <stdio.h> # include <stdlib.h> # include <iostream> # include <string.h> # include <math.h> using namespace std; # define IL inline # define RG register # define UN unsigned # define ll long long # define rep(i, a, b) for(RG int i = a; i <= b; i++) # define per(i, a, b) for(RG int i = b; i >= a; i--) # define uev(e, u) for(RG int e = ft[u]; e != -1; e = edge[e].nt) # define mem(a, b) memset(a, b, sizeof(a)) # define max(a, b) ((a) > (b)) ? (a) : (b) # define min(a, b) ((a) < (b)) ? (a) : (b) IL int Get(){ RG char c = '!'; RG int num = 0, z = 1; while(c != '-' && (c > '9' || c < '0')) c = getchar(); if(c == '-') z = -1, c = getchar(); while(c >= '0' && c <= '9') num = num * 10 + c - '0', c = getchar(); return num * z; } const int MAXN = 302, INF = 2147483647; struct Edge{ int to, nt; } edge[MAXN << 1]; int n, m, ft[MAXN], cnt, in[MAXN], w[MAXN], f[MAXN][MAXN]; IL void DP(RG int u){ rep(i, 1, m) f[u][i] = w[u]; uev(e, u){ RG int v = edge[e].to; DP(v); per(i, 2, m) per(j, 1, i - 1) f[u][i] = max(f[u][i], f[u][j] + f[v][i - j]); } } int main(){ mem(ft, -1); n = Get(); m = Get() + 1; rep(i, 1, n){ RG int v = Get(); w[i] = Get(); if(!v) continue; edge[cnt] = (Edge){i, ft[v]}; ft[v] = cnt++; in[i]++; } rep(i, 1, n) if(!in[i]) edge[cnt] = (Edge){i, ft[n + 1]}, ft[n + 1] = cnt++; DP(n + 1); printf("%lld\n", f[n + 1][m]); return 0; }
- 1
信息
- ID
- 197
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 6
- 标签
- 递交数
- 149
- 已通过
- 43
- 上传者