Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
运用多重背包来做 做之前先了解poj1837的做法这个题就相对来说简单了#include<stdio.h> #include<string.h> int bag[50]; int countbag; int num[7]; int f[3][240005]; int l[3]={0,-1,1}; int Cas=0; int main() { int i,j,k,temp,temp2; int total; //int mid; while(scanf("%d%d%d%d%d%d",num+1,num+2,num+3,num+4,num+5,num+6)&&(num[1]!=0||num[2]!=0||num[3]!=0||num[4]!=0||num[5]!=0||num[6]!=0)) { countbag=1; total=0; for(i=1;i<=6;i++) { total+=num[i]*i; } for(i=1;i<240005;i++) { f[1][i]=0; f[2][i]=0; } if(total%2) { printf("Collection #%d:\nCan't be divided.\n\n",++Cas); continue; } memset(bag,0,sizeof(bag)); for(i=1;i<=6;i++) { temp2=num[i]+1; k=1; while((temp2>>k)) k++; for(j=0;num[i]>=(1<<j)&&j<k-1;j++) { num[i]-=1<<j; bag[countbag++]=i*(1<<j);//rongliang } if(num[i]) { bag[countbag++]=i*num[i];//rongliang } } // for(i=1;i<countbag;i++) // printf("%d ",bag[i]); // printf("\n"); for(j=1;j<=2;j++) { f[1][120000+bag[1]*l[j]]++; // printf("%d %d\n",j,120000+bag[1]*l[j]); } // printf("**********************************\n"); for(i=2;i<countbag;i++) { for(j=1;j<=2;j++) { for(k=0;k<240005;k++) { temp=bag[i]*l[j]; if(k>temp) { if(f[1][k-temp]) { f[2][k]+=f[1][k-temp]; // printf("%d %d\n",i,k); if(i==countbag-1&&f[2][120000])goto flag; } } } } for(j=0;j<240005;j++) { f[1][j]=f[2][j]; f[2][j]=0; } } flag: if(f[2][120000]) printf("Collection #%d:\nCan be divided.\n\n",++Cas); else printf("Collection #%d:\nCan't be divided.\n\n",++Cas); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator