树形dp 结合01背包

1 #include
      
         2 #include
       
          3 #define max(a,b) a>b?a:b  4 const int INF = 1000000000;  5 const int maxn = 3010;  6 int head[maxn],dp[maxn][maxn],n,m;  7 int num[maxn];  8 struct EDGE{
     9     int v,w,next; 10 }edge[maxn]; 11 int  tot; 12 void add_edge(int s,int t,int w){
    13     edge[tot].v=t; 14     edge[tot].w=w; 15     edge[tot].next=head[s]; 16     head[s]=tot++; 17 } 18 void dfs(int u){
    19     int i,j,k,tmp[maxn]; 20     for(i=head[u];i!=-1;i=edge[i].next){
    21         int v=edge[i].v; 22         dfs(v); 23         for(j=0;j<=num[u];j++) 24             tmp[j]=dp[u][j]; 25          for(j = 0; j <= num[u]; j ++) 26             for(k = 1; k <= num[v]; k ++) 27                 dp[u][j+k] = max(dp[u][j+k], tmp[j]+dp[v][k]-edge[i].w); 28         num[u] += num[v];//利用回溯，自底向上的进行DP 29     } 30 } 31 int main(){
    32     int i,j,k,a,c; 33     tot=0; 34     memset(head,-1,sizeof(head)); 35     scanf("%d%d",&n,&m); 36     for(i=1;i<=n;i++) 37         for(j=1;j<=n;j++) 38             dp[i][j]=-INF; 39     for(i=1;i<=n-m;i++){
    40         scanf("%d",&k); 41         for(j=0;j
        
         =0;i--){
    53         if(dp[1][i]>=0){
    54             printf("%d\n",i); 55             break; 56         } 57     } 58     return 0; 59 }