P2014 选课


这是树上背包型问题

$f[i][j]$表示对于以$i$为根的子树中选$j$个获得的学分

则有$f[i][j]=min(f[i][j-k-1]+f[v][k]+w[v])$

之所以$j-k-1$是因为子树中肯定要取$v$,对于每一个子树,都进行这样的处理,就可以得出答案

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000;
int n,m,w[maxn],f[maxn][maxn];
vector<int> son[maxn];
void dfs(int u)
{
    for(int i=0;i<son[u].size();i++)
    {
        dfs(son[u][i]);
        for(int j=m;j>=0;j--)
            for(int k=j-1;k>=0;k--)
            f[u][j]=max(f[u][j-k-1]+f[son[u][i]][k]+w[son[u][i]],f[u][j]);
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) 
    {
        int x,y;
        scanf("%d%d",&x,&y);
        son[x].push_back(i);
        w[i]=y;
    }
    dfs(0);
    printf("%d\n",f[0][m]);
    return 0;
}

文章作者: songhn
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 songhn !
评论
 上一篇
对拍 对拍
在对拍时我们需要四个文件1. zj.cpp这是复杂度较有优但正确性未知的代码 2. baoli.cpp这是暴力但正确的代码 3. random.cpp这是随机生成数据的代码 4. duipai.cpp这是用于对拍的代码,在对拍时执行它的ex
2019-07-06
下一篇 
P1880 NOI1995石子合并 P1880 NOI1995石子合并
继续重新学dp,当年写的代码真是丑,一点缩进都没有… 基本区间dp,由于是环形,先复制一份然后继续求解,可以发现区间长度可以递增,把它作为状态,之后枚举左端点,求出右端点,然后在这中间枚举端点,进行更新。之后在扫一遍去最优就好了 #inc
2019-07-06
  目录