1.poj 2342

　　题意:邀请同事参加party，保证职员与直接上司不一起参加，每个人有个搞笑值，求邀请所有人的最大的搞笑值总和。

    DP部分：dp[0][i]表示职员i不来参加party，以i为根的子树的最大搞笑值，dp[1][i]表示职员i来参加party，以i为根的子树的最大搞笑值。

    所以DP状态转移方程为：

     　　dp[0][u] = 所有儿子v的(max(dp[0][v], dp[1][v]))之和;

    　　 dp[1][u] = 所有儿子v的(dp[0][v])之和 + val[u];

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5  6 using namespace std; 7 const int MAX=6005; 8  9 struct tree10 {11     int v,next;12 }edge[MAX];13 14 int k,val[MAX],head[MAX],le[MAX],rt[MAX],dp[2][MAX];15 16 void addedge(int u,int v)17 {18     edge[k].v=v;19     edge[k].next=head[u];20     head[u]=k++;21 }22 23 void dfs(int u)24 {25     int v,i;26     if(le[u])27     {28         dp[0][u]=0;29         dp[1][u]=val[u];30         return ;31     }32     for(i=head[u];i;i=edge[i].next)33     {34         v=edge[i].v;35         dfs(v);36         dp[0][u]+=max(dp[0][v],dp[1][v]);37         dp[1][u]+=dp[0][v];38     }39     dp[1][u]+=val[u];40 }41 42 int main()43 {44     int n,i,j,u,v;45     while(scanf("%d",&n)!=EOF)46     {47         memset(head,0,sizeof(head));48         memset(dp,0,sizeof(dp));49         k=1;50         for(i=1;i<=n;i++)51         {52             scanf("%d",&val[i]);53             le[i]=rt[i]=1;54         }55         for(i=1;;i++)56         {57             scanf("%d%d",&v,&u);58             if(v==0&&u==0)59                 break;60             addedge(u,v);61             rt[v]=le[u]=0;62         }63         for(i=1;i<=n;i++)64         {65             if(rt[i])66             {67                 dfs(i);68                 break;69             }70         }71         printf("%d\n",max(dp[0][i],dp[1][i]));72     }73     return 0;74 }
         
        
       
      

2.poj 3342

　　详解见本站博文《状态压缩DP与树形DP》

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5   6 using namespace std;  7 typedef long long ll;  8 int k,w,le[201],rt[201],head[201],dp[2][201],way[2][201];  9 char name[201][101]; 10  11 struct tree 12 { 13     int v,next; 14 }edge[201]; 15  16 void addedge(int u,int v) 17 { 18     edge[k].v=v; 19     edge[k].next=head[u]; 20     head[u]=k++; 21 } 22  23 int check(char* s) 24 { 25     int i; 26     for(i=0;i
          
           dp[1][v]&&way[0][v]==0) 53             way[0][u]=0; 54         if(dp[0][v]
           
            dp[1][0]) 91 { 92 ans=dp[0][0]; 93 if(way[0][0]) 94 flag=1; 95 } 96 else 97 { 98 ans=dp[1][0]; 99 if(dp[0][0]==dp[1][0])100 {101 if(way[0][0]+way[1][0]==1)102 flag=1;103 }104 else105 if(way[1][0])106 flag=1;107 }108 printf("%lld ",ans);109 if(flag)110 printf("Yes\n");111 else112 printf("No\n");113 }114 return 0;115 }
           
          
         
        
       
      

 3.poj 1947

　　题意：设定dp[i][j]为以i为根节点中有j个节点（包含i）的子树需要删除的边数。

　 　这里要用到背包，可以把p个节点的子树看作是容量，各个子树需要删除的边数为价值，要求得其价值最小。

 　　这道题的状态转移为dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[v][k])，

 　　但是要注意其初始化，以及dp[u][j]++;意思是每增加一个儿子，此时的dp[u][j]都需要多删一条边，

　　 然而之后却需要背包分配得出最小的dp[u][j]。

10654636    hankers    1947    Accepted    380K    0MS    C++    1404B    2012-08-11 10:50:49

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5  6 using namespace std; 7 const int MAX=350; 8 const int INF=100000; 9 10 struct tree11 {12     int v,next;13 }edge[MAX];14 int n,p,k,head[MAX],dp[MAX][MAX],visit[MAX];15 16 void addedge(int u,int v)17 {18     edge[k].v=v;19     edge[k].next=head[u];20     head[u]=k++;21 }22 23 void dfs(int u)24 {25     int i,j,v,kk;26     if(visit[u])27         return ;28     visit[u]=1;29     dp[u][1]=0;30     for(i=head[u];i;i=edge[i].next)31     {32         v=edge[i].v;33         if(!visit[v])34         {35             dfs(v);36             for(j=p;j>=1;j--)37             {38                 dp[u][j]++;39                 for(kk=1;j-kk>0;kk++)40                     dp[u][j]=min(dp[u][j],dp[u][j-kk]+dp[v][kk]);41             }42         }43     }44 }45 46 int main()47 {48     int u,v,i,j,ans;49     while(scanf("%d%d",&n,&p)!=EOF)50     {51         memset(head,0,sizeof(head));52         memset(visit,0,sizeof(visit));53         k=1;54         for(i=1;i<=n;i++)55             for(j=1;j<=p;j++)56                 dp[i][j]=INF;57         for(i=1;i
          
           dp[i][p]+1)67                 ans=dp[i][p]+1;68         printf("%d\n",ans);69     }70     return 0;71 }
          
         
        
       
      

4.hdu 1561

　　题意:给出多组边（a,b）代表攻克a才可以攻克b,每个点都有权值，要求攻克M个点所得最大权值。

首先将其构造为一个树，0为根节点，即可以使用背包算法得出结果，其中注意的是初始化时，dp[u][1]=num[u];

6519139    2012-08-11 15:02:12    Accepted    1561    93MS    540K    1357 B    C++    hanker

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5  6 using namespace std; 7 const int MAX=350; 8 const int INF=1000000; 9 10 struct tree11 {12     int v,next;13 }edge[MAX];14 15 int n,m,k,head[MAX],dp[MAX][MAX],num[MAX],visit[MAX];16 17 void addedge(int u,int v)18 {19     edge[k].v=v;20     edge[k].next=head[u];21     head[u]=k++;22 }23 24 void dfs(int u)25 {26     int i,j,v,kk;27     if(visit[u])28         return ;29     visit[u]=1;30     dp[u][1]=num[u];31     for(i=head[u];i!=-1;i=edge[i].next)32     {33         v=edge[i].v;34         if(!visit[v])35         {36             dfs(v);37             for(j=m+1;j>=1;j--)38             {39                 for(kk=1;kk
         
        
       
      

5.

待续...