题解 P6223 【 [COCI 2009] PODJELA】
Mr_Eight
·
·
题解
很典型的一道树形DP
首先简化一下题目：每个人有 x- v_{i}块钱（可为负）。要求出使所有人的钱数都 ≥0。
DP状态确立
设 dp_{i,j} 为在节点为 i 的子树内进行 j 次操作，使除 i 号节点外，i 的所有子节点的钱数都 ≥0 时（符合要求），i 号节点最多能有的钱数（若为负数，则意为还需要父节点给自己的钱数）。
DP转移式
对于每一个节点，每添加一颗子树时，
```cpp
next[pos][j+k+1]=max(next[pos][j+k+1],dp[pos][j]+dp[c[pos][i]][k])
```
其中 $pos$ 是该节点， $c[pos][i]$ 表示正在添加的子树。
$(2)$当 $dp[c[pos][i]][k]$ $≥0$ 时，可以不将子节点的钱向上运：
```cpp
if(dp[c[pos][i]][k]>=0){
next[pos][k+j]=max(next[pos][k+j],dp[pos][j]);
}
```
### 附上丑陋的代码（仅删去头文件部分）
```cpp
#define F(i,a,b) for(register int i=a,i##end=b;i<=i##end;++i)
using namespace std;
int read() {
int x=0;
bool fu=0;
char ch=0;
while(ch>'9'||ch<'0') {
ch=getchar();
if(ch=='-')fu=1;
}
while(ch<='9'&&ch>='0') x=(x*10+ch-48),ch=getchar();
return fu?-x:x;
}
int n,t1,t2,x,v[2002],f[2002],dp[2002][2002],size[2002],next[2002][2002];
bool vis[2002];
vector<int>g[2002],c[2002];
void make_tree(int pos) {
vis[pos]=1;
if(g[pos].size()<=1 && pos!=1) {
size[pos]=1;
return;
}
size[pos]=1;
F(i,0,g[pos].size()-1) {
if(!vis[g[pos][i]]) {
c[pos].push_back(g[pos][i]);
f[g[pos][i]]=pos;
make_tree(g[pos][i]);
size[pos]+=size[g[pos][i]];
}
}
}
void DP(int pos) {
int ssize=0;
F(i,0,c[pos].size()-1) {
DP(c[pos][i]);
}
F(i,0,c[pos].size()-1) {
F(j,0,2001) {
next[pos][j]=(-INT_MAX)/3;
}
F(j,0,ssize) {
F(k,0,size[c[pos][i]]-1) {
next[pos][j+k+1]=max(next[pos][j+k+1],dp[pos][j]+dp[c[pos][i]][k]);
if(dp[c[pos][i]][k]>=0) {
next[pos][k+j]=max(next[pos][k+j],dp[pos][j]);
}
}
}
F(j,0,2000) {
dp[pos][j]=next[pos][j];
}
ssize+=size[c[pos][i]];
}
}
int main() {
memset(dp,-0x1f,sizeof(dp));
cin>>n>>x;
F(i,1,n) {
v[i]=x-read();
dp[i][0]=v[i];
}
F(i,2,n) {
t1=read(),t2=read();
g[t1].push_back(t2);
g[t2].push_back(t1);
}
make_tree(1);//建树
DP(1);//DP
F(i,0,2000) {//输出答案
if(dp[1][i]>=0) {
cout<<i;
return 0;
}
}
return 0;
}
```
~~记得双击，么么哒（~~