【Luogu 2014】选课

佚名 6年前 (2019-05-05) 随笔 884人围观抢沙发百度已收录

【题目链接】传送门

【调试出错】

写了第一遍怎么调都不过，气得想摔键盘。

冷静去上了两节文化课回来又码了一遍，然后就一遍过了。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

【code】

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int x = 0,f = 1; char ch = getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0'; ch=getchar();}
    return x*f;
}
const int mxn = 200+5;
int n,m;
int s[mxn],f[mxn][mxn];
#define pb push_back
vector<int> son[mxn];
inline void dp(int x){
    f[x][0] = 0;
    for(int i = 0;i < son[x].size(); ++i){
        int y = son[x][i];
        dp(y);
        for(int j = m; j >= 0; --j)
            for(int t = j; t >= 0; --t)
                if(j-t>=0) f[x][j] = max(f[x][j],f[x][j-t]+f[y][t]);
    }
    if(x) for(int t = m; t; --t) f[x][t] = f[x][t-1]+s[x];
}
int main(){
//    freopen("test.in","r",stdin);
//    freopen("test.out","w",stdout);
    n = read(),m = read();
    for(int i = 1;i <= n; ++i){
        int x;
        x = read(),s[i] = read();
        son[x].pb(i);
    }
    memset(f,0xcf,sizeof f);
    f[0][0] = 0;
    printf("%d\n",f[0][m]);
    return 0;
}