首页 > 代码库 > [codevs1378]选课
[codevs1378]选课
传送门
f[i][j]代表以在节点i和它的子树中选j门课时可以达到的最大学分。
1 #include<cstdio> 2 #include<vector> 3 #include<iostream> 4 #include<algorithm> 5 using namespace std; 6 7 inline void read(int &ans) { 8 static char ch = getchar(); 9 register int neg = 1; 10 ans = 0; 11 for (; !isdigit(ch); ch = getchar()) 12 if (ch == ‘-‘) neg = -1; 13 for (; isdigit(ch); ch = getchar()) 14 ans = ans * 10 + ch - ‘0‘; 15 ans *= neg; 16 } 17 const int N = 310; 18 vector < int > g[N]; 19 int n, m, f[N][N], w[N]; 20 inline void init() { 21 read(n); read(m); 22 for (int a, i = 1; i <= n; ++i) { 23 read(a); read(w[i]); 24 g[a].push_back(i); 25 } 26 } 27 28 void dp(int u) { 29 int size = g[u].size(); 30 for (int i = 0; i < size; ++i) { 31 int &v = g[u][i]; 32 dp(v); 33 for (int j = m; j >= 1; --j) { 34 for (int k = 1; k <= j; ++k) { 35 f[u][j] = max(f[u][j], f[u][j - k] + f[v][k]); 36 } 37 } 38 } 39 if (u) for (int i = m; i >= 1; --i) f[u][i] = f[u][i - 1] + w[u]; 40 } 41 42 int main() { 43 init(); 44 dp(0); 45 printf("%d\n", f[0][m]); 46 return 0; 47 }
[codevs1378]选课
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。