选课

ゝ一世哀愁。 2022-01-08 00:27 292阅读 0赞

[选课][Link 1]

有n门课程，第i门课程的学分为\\(a\_i\\)，每门课程最多有一个先修课程，表示只有选了这一门课程才能选另一门课程，现在要从中选出m个课程，求最大的学分之和，\\(1≤N≤300\\)。

### 解 ###

有依赖的问题经常是树形递推，肯定要表现选到哪一个节点，自然也要表现选了几门课，于是设\\(f\[x\]\[y\]\\)表示以第x门课程为根节点的子树中选了y门课程的学分之和，\\(x\_i\\)为节点x的第x个儿子。

然后又注意到问题是森林，于是可以把每一棵树的根节点并到同一个根节点0,组成一棵树，因此不难有

\\\[f\[x\]\[y\]=\\max\_\{\\sum\_\{i=1\}^\{|son(x)|\}k\_i=y-1\}(\\sum\_\{i=1\}^\{|son(x)|\}f\[x\_i\]\[y\_i\])+a\_x\\\]

注意到其实是确定了选多少门课，再从每一棵子树中选出一些课，让选的课数纸盒正好为y-1,类似与分组背包，于是转移方程可以转换为，对于其子树\\(x\_i\\)而言

\\\[f\[x\]\[y\]=\\max\_\{j=0\}^\{\\min(y-1,m)\}(f\[x\]\[y-j\]+f\[x\_i\]\[j\])\\\]

边界：\\(f\[x\]\[0\]=0,f\[x\]\[1\]=a\_x,i=0,1,2,...,n\\)，其余负无限大

参考代码：

dfs

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #define il inline
    #define ri register
    using namespace std;
    struct point{
        point*next;int to;
    }*pt,*head[301];
    int n,m,in[301],dp[301][302];
    il void read(int&),link(int,int);
    void dfs(int);il int max(int,int);
    int main(){
        read(n),read(m),memset(dp,-10,sizeof(dp));
        for(int i(1),j;i<=n;++i){
            read(j),read(dp[i][1]);
            if(j)link(j,i),++in[i];
        }++m;
        for(int i(1);i<=n;++i)if(!in[i])link(0,i);
        dfs(0),printf("%d",dp[0][m]);
        return 0;
    }
    il int max(int a,int b){
        return a>b?a:b;
    }
    void dfs(int x){
        dp[x][0]=0;
        for(point *i(head[x]);i!=NULL;i=i->next){
            dfs(i->to);
            for(int j(m),k;j;--j)
                for(k=j-1;k;--k)
                    dp[x][j]=max(dp[x][j],dp[x][j-k]+dp[i->to][k]);
        }
    }
    il void link(int u,int v){
        pt=new point,pt->to=v;
        pt->next=head[u],head[u]=pt;
    }
    il void read(int &x){
        x&=0;ri char c;while(c=getchar(),c<'0'||c>'9');
        while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    }

bfs

#include <iostream>
    #include <cstdio>
    #include <queue>
    #include <cstring>
    #define il inline
    #define ri register
    using namespace std;
    queue<int>T;
    int in[301],pa[301],n,m,
        dp[301][302];
    il void read(int&);
    il int dag(),max(int,int);
    int main(){
        read(n),read(m),memset(dp,-10,sizeof(dp));
        for(int i(1),j;i<=n;++i)
            read(j),read(dp[i][1]),
                ++in[j],pa[i]=j,dp[i][0]=0;
        ++pa[0],++m,printf("%d",dag());
        return 0;
    }
    il int max(int a,int b){
        return a>b?a:b;
    }
    il int dag(){
        dp[0][0]=dp[0][1]=0;
        for(int i(1);i<=n;++i)if(!in[i])T.push(i);
        while(!T.empty()){
            int s(T.front());T.pop();
            for(int i(m);i;--i)
                for(int j(i-1);j;--j)
                    dp[pa[s]][i]=max(dp[pa[s]][i],dp[pa[s]][i-j]+dp[s][j]);
            --in[pa[s]];if(!in[pa[s]])T.push(pa[s]);
        }return dp[0][m];
    }
    il void read(int &x){
        x&=0;ri char c;while(c=getchar(),c<'0'||c>'9');
        while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    }

转载于:https://www.cnblogs.com/a1b3c7d9/p/10927406.html

[Link 1]: http://contest-hunter.org:83/contest/0x50%E3%80%8C%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E3%80%8D%E4%BE%8B%E9%A2%98/5402%20%E9%80%89%E8%AF%BE