第一道水出来(chaotijie）的省选题目
题目描述
现在我们的手头有N个软件，对于一个软件i，它要占用Wi的磁盘空间，它的价值为Vi。我们希望从中选择一些软件安装到一台磁盘容量为M计算机上，使得这些软件的价值尽可能大（即Vi的和最大）。
但是现在有个问题：软件之间存在依赖关系，即软件i只有在安装了软件j（包括软件j的直接或间接依赖）的情况下才能正确工作（软件i依赖软件j)。幸运的是，一个软件最多依赖另外一个软件。如果一个软件不能正常工作，那么它能够发挥的作用为0。
我们现在知道了软件之间的依赖关系：软件i依赖软件Di。现在请你设计出一种方案，安装价值尽量大的软件。一个软件只能被安装一次，如果一个软件没有依赖则Di=0，这时只要这个软件安装了，它就能正常工作。
输入输出格式
输入格式：
第1行：N, M （0<=N<=100, 0<=M<=500）
第2行：W1, W2, ... Wi, ..., Wn （0<=Wi<=M ）
第3行：V1, V2, ..., Vi, ..., Vn （0<=Vi<=1000 ）
第4行：D1, D2, ..., Di, ..., Dn （0<=Di<=N, Di≠i ）
输出格式：
一个整数，代表最大价值
输入输出样例
输入样例#1：
3 10
5 5 6
2 3 4
0 1 1
输出样例#1：
5
这道题一开始写的是树形DP，我以为跟选课一样，后来被张老师告知有环，瞬间蒙蔽，只能AC第二点（输出为0）。这个题的环是因为这个神奇的依赖关系。比如A-B-C-D-A，你任选一个其中的 必然别的也都得选，选了A你就得选D，选了D又得选C.....那么这些点就是一个点了，要么选要么不选。 再讲讲DP方程：有两类解法一种是我写选课时候的解法，以x为根节点，分配j的资源那么这样的转移必然是
F[x][j]=max(F[x][j],f[x][j-k]+dp(child[i],k))
这意思也很明了，就是说你已经选了几颗子树，得到了最优解，那么看看分配给新树资源能不能得到新的答案。
另一种更好的，也是我从一位洛谷神犇上学到的，就是不选择分配多少资源，直接选择头部递归，得到F[child[i][j]的所有状态，方程应该是F[i][j]=max(F[x][j],f[x][j-k]+f[child[i]][k])，这里的两个方程都必须是逆序枚举J，原因很简单，我们依赖F[X][J-K]这个状态更新，所以不能和当前状态重复。方程细节参考代码.
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
struct tr{
int x;
int size;
int w;
int v;
int ch[10005];
int fai;
};
tr a[1005];
int f[10005][1005];
int dfs(int x, int w)
{
if(f[x][w]!=-1)
return f[x][w];
if(w==0)
{
f[x][w]=0;
return 0;
}
if(a[x].w>w)
{
f[x][w]=0;
return 0;
}
if(a[x].size==0&&a[x].w<=w)
{
f[x][w]=a[x].v;
return a[x].v;
}
int i, j, k;
for(i=1;i<=a[x].size;i++)
{
for(j=w;j>=a[i].w;j--)
{
if(i==1)
{
f[x][j]=a[x].v+dfs(a[x].ch[i],j-a[x].w);
}
else
{
for(k=j-a[x].w;k>=1;k--)
{
f[x][j]=max(f[x][j],f[x][j-k]+dfs(a[x].ch[i],k));
}
}
}
}
return f[x][w];
}
int cnt;
int main()
{
// freopen("a.in","r",stdin);
// freopen("a.out","w",stdout);
int N, M;
int i,j,k;
cin>>N>>M;
for(i=1;i<=1005;i++)
{
for(j=1;j<=1005;j++)
{
f[i][j]=-1;
}
}
for(i=1;i<=N;i++)
{
a[i].size=0;
}
for(i=1;i<=N;i++)
{
cin>>a[i].w;
}
for(i=1;i<=N;i++)
{
cin>>a[i].v;
}
for(i=1;i<=N;i++)
{
int t;
cin>>t;
if(t==0)
a[i].fai=1;
a[t].ch[++a[t].size]=i;
}
for(i=1;i<=N;i++)
{
if(a[i].fai)
dfs(i,M);
}
for(i=1;i<=N;i++)
{
if(a[i].fai)
{
for(j=M;j>=1;j--)
{
for(k=j;k>=1;k--)
f[0][j]=max(f[0][j],f[i][k]+f[0][j-k]);
}
}
}
cout<<f[0][M];
return 0;
// cout<<f[0][M];
}
