Poj Solution 1155

```http://poj.org/problem?id=1155

/* @author: */
import java.util.*;
import java.util.Scanner;
public class Main{

static  int[][] dp;
static int[] offspring;
static int[] vert;
static int[] parent;
static int[] leaf;
static int n,k;
public static void main(String[] args)
{
Scanner cin=new Scanner(System.in);
n=cin.nextInt();
leaf=new int[n+1];
offspring=new int[n+1];
vert=new int[n+1];
parent=new int[n+1];
dp=new int[n+1][n+1];
boolean[] flag=new boolean[n+1];
int[] left=new int[n+1];
int[] right=new int[n+1];
for(int i=0;i<=n;i++)
for(int j=0;j<=n;j++)
{
if(j==0)
dp[i][j]=0;
else
dp[i][j]=-99999999;
}
k=cin.nextInt();
for(int i=0;i< n-k;i++)
{
int c=cin.nextInt();
if(c==0)
continue;
int temp=i+1;
int m=cin.nextInt();
vert[m]=cin.nextInt();
left[temp]=m;
parent[m]=temp;
offspring[temp]+=1;
temp=m;
for(int j=1;j< c;j++)
{
m=cin.nextInt();
right[temp]=m;
parent[m]=temp;
offspring[temp]+=2;
vert[m]=cin.nextInt();
temp=m;
}
}
for(int i=0;i< k;i++)
{
int m=i+n-k+1;
while(m!=0)
{
leaf[m]++;
m=parent[m];
}
}
for(int i=0;i < k;i++)
{
dp[i+n-k+1][1]=cin.nextInt()-vert[i+n-k+1];
if(offspring[i+n-k+1]==0)
flag[i+n-k+1]=true;
}
while(!flag[1])
{
for(int i=1;i<=n;i++)
{
if(!flag[i])
{
int l=left[i];
int r=right[i];
if(l==0&&flag[r])
{
for(int o=leaf[i];o>=0;o--)
for(int p=leaf[r];p>=0;p--)
{
if(o+p<=leaf[i]&&dp[r][p]+dp[i][o]>dp[i][o+p])
dp[i][o+p]=dp[r][p]+dp[i][o];
}
int o=0;
while(o<=leaf[r])
{
if(dp[r][o]>dp[i][o])
dp[i][o]=dp[r][o];
o++;
}
flag[i]=true;
}
if(r==0&&flag[l])
{
for(int o=leaf[i];o>=0;o--)
for(int p=leaf[l];p>=0;p--)
{
if(o+p<=leaf[i]&&dp[l][p]+dp[i][o]-vert[i]>dp[i][o+p])
dp[i][o+p]=dp[l][p]+dp[i][o]-vert[i];
}
int o=0;
while(o<=leaf[l])
{
if(dp[l][o]-vert[i]>dp[i][o])
dp[i][o]=dp[l][o]-vert[i];
o++;
}
flag[i]=true;
}
if(flag[r]&&flag[l])
{
for(int o=leaf[r];o>=0;o--)
for(int p=leaf[l];p>=0;p--)
{
if(p!=0)
{
if(o+p<=leaf[i]&&dp[l][p]+dp[r][o]-vert[i]>dp[i][o+p])
dp[i][o+p]=dp[l][p]+dp[r][o]-vert[i];
}
if(p==0)
{
if(dp[r][o]>dp[i][o])
dp[i][o]=dp[r][o];
}

}
flag[i]=true;
}
}
}
}
int i;
for(i=k;i>=1;i--)
{
if(dp[1][i]>=0)
break;
}
System.out.println(i);
}
}
```
This entry was posted in poj. Bookmark the permalink.