HDU1059 Dividing

这题做了半天 ,明明就是套模板的题,不知道怎么老是WA...

顺便说一下这题还有DFS解法;

 1 #include<iostream>
 2  using namespace std;
 3  const int maxn = 10;
 4  int n[ maxn ];
 5  int sumv,V;
 6  int dp[ 60011 ];
 7  int max(int a,int b)
 8  {
 9      return a>b?a:b ;
10  }
11  void bag01( int cost,int weight ){
12      for( int i=V;i>=cost;i-- ){
13          dp[ i ]=max(dp[ i ],dp[ i-cost ]+weight);
14      }
15      return ;
16  }
17  void bagall( int cost ,int weight ){
18     for( int i=cost;i<=V;i++ ){
19         dp[ i ]=max( dp[ i ],dp[ i-cost ]+weight);
20     }
21      return ;
22  }
23  
24 void mul_bag( int cost,int weight,int num ){
25      if( cost*num>=V ){
26          bagall( cost,weight );
27          return ;
28     }
29      int k=1;
30      while( k<=num ){
31          bag01( k*cost,k*weight );
32          num-=k;
33          k*=2;
34     }
35      bag01( num*cost,num*weight );
36      return ;
37  }
38  int main()
39  {
40      int i,k=1;
41      while(cin>>n[0]>>n[1]>>n[2]>>n[3]>>n[4]>>n[5],n[0]+n[1]+n[2]+n[3]+n[4]+n[5])
42      {
43          memset(dp,0,sizeof(dp));
44         sumv=n[0]+n[1]*2+n[2]*3+n[3]*4+n[4]*5+n[5]*6;
45          if(sumv%2==1)
46          {
47              printf("Collection #%d:
Can't be divided.

",k++);
48              continue;
49          }
50          V=sumv/2;
51         for(i=0;i<6;i++)
52         {
53              if(n[i]) mul_bag(i+1,i+1,n[i]);
54         }
55         if(V==dp[V]) printf("Collection #%d:
Can be divided.

",k++);
56          else printf("Collection #%d:
Can't be divided.

",k++);
57      }
58      return 0;
59  }

这题的DFS解法.

 1 #include<iostream>  
 2 #include<cstdio>  
 3 using namespace std;  
 4 int halfvalue;  
 5 int a[7],sum,SUM,flag;  
 6   
 7 void dfs(int v,int pre) 
 8 {                        
 9     if(flag==1)    
10         return;  
11     if(v==halfvalue)  
12     {  
13         flag=1;  
14         return;  
15     }  
16     for(int i=pre;i>=1;i--)  
17     {  
18        if(a[i]!=0)  
19        {  
20            if(v+i<=halfvalue)  
21            {  
22                a[i]--;//用过了就要减 
23                dfs(v+i,i);  
24                if(flag==1)  
25                    break;  
26            }  
27        }  
28     }  
29     return;  
30 }  
31 int main()  
32 {  
33     int c=1;  
34     while(1)  
35     {  
36         sum=0,SUM=0;  
37         for(int i=1;i<=6;i++)  
38         {  
39             scanf("%d",&a[i]);  
40             sum+=a[i];  
41             SUM+=i*a[i];  
42         }  
43         if(sum==0)  
44             break;  
45         if(SUM%2==1)  
46         {  
47             printf("Collection #%d:
Can't be divided.

",c++);  
48             continue;  
49         }  
50         flag=0;  
51         halfvalue=SUM/2;  
52         dfs(0,6);  
53         if(flag==1)  
54             printf("Collection #%d:
Can be divided.

",c++);  
55         else  
56             printf("Collection #%d:
Can't be divided.

",c++);  
57     }  
58     system("pause");  
59     return 0;  
60 }