解题报告 P2014 [CTSC1997]选课

题目内容

P2014

大意:选课,其中选某些课必须选一个先修课,每门课有一个学分,求选 m 门课达到的最大学分

解题思路

树上的 0-1 背包问题,具体的思路还是递归求解每一棵子树的最优解。

f_{now,j} 表示以 now 节点为根的子树选 j 门课(包括 now 本身)能达到的最大学分。则有状态转移方程

f_{now,j}=\max\lbrace f_{now,j},f_{x,k}+f_{now,j-k} \rbrace

其中 xnow 的儿子节点,k\in[0,j)j\in[1,m+1]

还有一点需要注意的是我们可以假设出一个 0 节点,作为整棵树的根,方便进行处理。

#include <cstdio>
#include <vector>
#include <cctype>
using namespace std;

const int maxn=305;
int n,m,s[maxn],f[maxn][maxn];
vector<int> son[maxn];

inline int read()
{
    bool w=0;
    int x=0;
    char c=getchar();
    while(!isdigit(c))
    {
        if(c=='-')
            w=1;
        c=getchar();
    }
    while(isdigit(c))
        x=x*10+c-'0',c=getchar();
    return w?-x:x;
}

void dfs(int now)
{
    for(auto i:son[now])
    {
        dfs(i);
        for(int j=m+1;j>=1;--j)
            for(int k=0;k<j;++k)
                f[now][j]=max(f[now][j],f[now][j-k]+f[i][k]);//转移
    }
    return;
}

int main()
{
    n=read(),m=read();
    for(int i=1,k;i<=n;i++)
    {
        k=read(),s[i]=read();
        f[i][1]=s[i];//初始值
        son[k].push_back(i);
    }
    dfs(0);
    printf("%d\n",f[0][m+1]);
    return 0;
}

“解题报告 P2014 [CTSC1997]选课”的2个回复

发表评论

电子邮件地址不会被公开。 必填项已用*标注