#10154. 「一本通 5.2 例 2」选课

2019-01-30 15:27:46


10154. 「一本通 5.2 例 2」选课

题意

有很多课程,但部分课程有先修课。学生不可能学完大学开设的所有课程,因此必须在入学时选定自己要学的课程。每个学生可选课程的总数是给定的。请找出一种选课方案使得你能得到的学分最多,并满足先修课优先的原则。假定课程间不存在时间上的冲突。

思路

瞎搞树形DP。

发现这是背包。

还是分组背包。(^▽^)

于是就愉快地解决了。

设 $f[x][t]$ 表示以x为根节点的子树中选t门课能够获得的最高学分。(所以说是背包问题嘛) $$Answer:f[0][m]$$

#include<algorithm>
#include<bitset>
#include<complex>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#include<cstring>
#include<cmath>
#define ll long long 
#define eps 1e-4
using namespace std;
inline int read(){
    int ret=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-f;ch=getchar();}
    while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
inline void write(int zx){
    if(zx<0){zx=-zx;putchar('-');}
    if(zx<10) putchar(zx+'0');
    else{
        write(zx/10);
        putchar(zx%10+'0');
    }
}
int n,m,fir[310],nxt[310];
int s[310],w[310],f[310][310];
int DP(int x){
    if(fir[x]==-1) return 0;
    int sum=0;
    for(int i=fir[x];i!=-1;i=nxt[i]){
        int tmp=DP(i);
        sum+=tmp+1;
        for(int j=sum;j>=0;j--)
            for(int k=0;k<=tmp;k++)
                if(j-k-1>=0) f[x][j]=max(f[x][j],f[x][j-k-1]+f[i][k]);
    }
    return sum;
}
int main(){
    n=read();m=read();
    memset(fir,-1,sizeof(fir));
    for(int i=1;i<=n;i++){
        s[i]=read();w[i]=read();
        nxt[i]=fir[s[i]];
        fir[s[i]]=i;
    }
    for(int i=1;i<=n;i++) f[i][0]=w[i];
    f[0][0]=0;
    DP(0);
    write(f[0][m]);
    putchar('\n');
    return 0;
}