随笔-65  评论-6  文章-0  trackbacks-0
 1 /*
 2 Author:    Leo.W
 3 Descriptipn:    几个价值不一的大理石,是否能够两个人价值均分
 4 How to Do:    先求的价值均分时的理论值ave_value,判断奇偶;若为偶数则转为完全背包问题求解,由于数量较大,可以模10以减小问题
 5                    规模,再DP求解,关键的是初始化dp[0]=0及dp数组初始为int类型的最小值。当得到dp[sum]>0,即存在一组可行解满足dp[0]开始取到sum。
 6   */
 7 #include <stdio.h>
 8 #include <string.h>
 9 #define MAXSIZE 120002
10 #define inf 0x7fffffff
11 #define max(x,y) x>y?x:y
12 int dp[MAXSIZE];
13 int value[6];
14 int main(){
15     //freopen("in.txt","r",stdin);
16     int i,j,k,no=1;
17     while(scanf("%d",&value[0])){
18         scanf("%d%d%d%d%d",&value[1],&value[2],&value[3],&value[4],&value[5]);
19         if(value[0]+value[1]+value[2]+value[3]+value[4]+value[5]==0)
20             break;
21         printf("Collection #%d:\n",no++);
22         int sum=0;
23         for(i=0;i<6;i++){
24             value[i]%=10;
25             sum+=value[i]*(i+1);
26         }
27         if(sum&1){
28             printf("Can't be divided.\n\n");    continue;
29         }    
30         sum/=2;
31         for(i=0;i<MAXSIZE;i++)    dp[i]=-inf-1;
32         dp[0]=0;
33         for(i=1;i<=6;i++){
34             for(j=1;j<=value[i-1];j++){
35                 for(k=sum;k>=i;k--){
36                     dp[k]=max(dp[k],dp[k-i]+1);
37                 }
38             }
39         }
40         if(dp[sum]>0)    printf("Can be divided.\n\n");
41         else    printf("Can't be divided.\n\n");
42 
43     }
44     return 0; 
45 } 
posted on 2012-03-07 15:03 Leo.W 阅读(460) 评论(3)  编辑 收藏 引用

评论:
# re: hdu 1059(Dividing) 2012-05-02 09:25 | 笨蛋侦探
为什么 value[i] %= 10 对结果没有影响?  回复  更多评论
  
# re: hdu 1059(Dividing) 2012-05-03 15:09 | Leo.W
每类大理石多于10的部分总是可以按价值且同时按数目等分给甲乙@笨蛋侦探
  回复  更多评论
  
# re: hdu 1059(Dividing) 2012-07-06 12:44 | xxxxxxxxxxxxxxxxxxxxxxxx
%10 真心不科学 比如 30 0 1 0 1 0

其中第一个数与10取余数,就成0,实际上 只要第一个数是大于等于2以上的偶数, 答案都应该是can。变成0之后就是cannot了  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理