题目链接：http://www.tyvj.cn/p/1051
题解：
设dp[i][j] = 第i门课选课程j的最大学分，vis[i][j][k]标记第i门课选课程j时选修课k是否选择，par[i]表示i的先修课程（无先修课程的默认先修课程为课程0）
则dp[i][j] = max(dp[i-1][k]+w[j])（vis[i-1][k][par[j]] && !vis[i-1][k][j]）
#include<iostream> #include<stdio.h> #include<algorithm> #include<cmath> #include<stdlib.h> #include <string.h> #include<queue> #include<set> #include<map> #include<stack> #include<time.h> using namespace std; #define MAX_N 100005 #define inf 0x3f3f3f3f #define LL long long #define ull unsigned long long const LL INF = 1e18; const int mod = 1e8+7; typedef pair<int, int>P; int par[305]; int dp[305][305]; bool vis[305][305][305]; int w[305]; int main() { int N, M; cin >> N >> M; for(int i=1; i<=N; i++) cin >> par[i] >> w[i]; for(int j=0; j<=N; j++) vis[0][j][0] = true; for(int i=1; i<=M; i++) { for(int j=1; j<=N; j++) { int c = -1; for(int k=0; k<=N; k++) { if(!vis[i-1][k][j] && vis[i-1][k][par[j]] && (c==-1 || dp[i-1][c]<dp[i-1][k])) c = k; } if(c != -1) { //printf("%d %d %d---\n", i, j, c); for(int k=0; k<=N; k++) vis[i][j][k] = vis[i-1][c][k]; vis[i][j][j] = true; dp[i][j] = dp[i-1][c] + w[j]; } } }/* for(int i=1; i<=M; i++) for(int j=1; j<=N; j++) printf("%d%c",dp[i][j],j==N?'\n':' ');*/ int ans = 0; for(int i=1; i<=N; i++) ans = max(ans, dp[M][i]); cout << ans << endl; } /* 6 4 0 4 1 3 2 2 3 1 1 1 5 3 */
