题目传送门; https://www.luogu.org/problemnew/show/P2014
我觉得题目给出 0 节点作为虚拟课程, 也避免了我们要去想将若干个森林建成一棵树; 将 N 个节点的森林建成了 N+1 条边的树;
其次, 我们对这个题进行一个分析;
很容易想到 F[x,t] 表示以 x 为根的子树中, 选择 t 门课程所获得得最高学分;
在 x 的子树中选择节点 y, 再以 y 为根的子树中, 选择 c_i 门课程, 保证Σc_i = t - 1;
初始状态, t=0 时, F[x,t] =0;
通过分析状态转移方程, 该方程实际上是一个分组背包模型, 第 i 组的第 j 个物品体积为 j, 价值为 F[y,j], 背包总容积 t-1;
我们要从每组中选择不超过 1 个物品 (每个子节点 y 都只能选择一个状态转移到 x), 在选择总物品不超过 t-1 的前提下, 学分最大;
是背包与树形 DP 的结合;
- #include<bits/stdc++.h>
- using namespace std;
- int lin[1000],tot,n,m,x,f[400][400],s[400];
- template<typename T>inline void read(T &x)
- {
- x=0;T f=1,ch=getchar();
- while(!isdigit(ch)) {if(ch=='-') f=-1; ch=getchar();}
- while(isdigit(ch)) {x=x*10+ch-'0'; ch=getchar();}
- x*=f;
- }
- struct gg {
- int y,next;
- }a[2000];
- inline void add(int x,int y) {
- a[++tot].y=y;
- a[tot].next=lin[x];
- lin[x]=tot;
- }
- inline void dp(int x) {
- f[x][0]=0;
- for(int i=lin[x];i;i=a[i].next) {
- int y=a[i].y;
- dp(y);
- // 倒序循环当前选课总门数, 或者背包的总体积;
- for(int t=m;t>=0;--t) {
- // 循环更深子树上的选课门数 (组内物品);
- // 此处倒序是为了正确处理组内体积为 0 的物品, 这样可以从初始状态 f[x,0] 转移;
- for(int j=t;j>=0;--j) {
- if(t-j>=0) {
- f[x][t]=max(f[x][t],f[x][t-j]+f[y][j]);
- }
- }
- }
- }
- if(x!=0) {//x!=0, 选修 x 本身需要占用 1 节课, 获得相应的学分;
- for(int t=m;t>0;t--)
- f[x][t]=f[x][t-1]+s[x];
- }
- }
- int main() {
- read(n);read(m);
- for(int i=1;i<=n;i++) {
- read(x);
- add(x,i);
- read(s[i]);
- }
- dp(0);
- cout<<f[0][m]<<endl;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3050603.html