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 |
Re:最强的剪枝In Reply To:最强的剪枝 Posted by:yihuikang at 2012-07-26 20:13:21 > 事实上当某种石头个数太大的时候,截掉一截即可, > 我的处理是: > if (x>60) > if (x%2) x=61; > else x=60; > 这样数据范围就很小了,怎么做都能过~ > 为什么是60? > 因为1~6的最小公倍数是60。 谢谢咯~ #include<iostream> #include<cstring> #include<algorithm> using namespace std; int data[7]; bool flag[200000]; int to; int sum; //int num; int main(){ for(int to=1;;to++){ sum = 0; //num = 0; for(int i=1;i<=6;i++){ cin>>data[i]; if(data[i]>60) if(data[i]%2) data[i] = 61; else data[i] = 60; sum = sum + data[i]*i; //num = num + data[i]; } if(sum==0) break; if(sum%2!=0){ cout<<"Collection #"<<to<<":"<<endl; cout<<"Can't be divided."<<endl; cout<<endl; continue; } memset(flag,false,sizeof(flag)); flag[0] = true; for(int i=1;i<=6;i++){ for(int j=0;j<data[i];j++){ for(int k=sum/2;k>=0;k--){ if(flag[k]) flag[k+i] = true; } } } if(flag[sum/2]==1){ cout<<"Collection #"<<to<<":"<<endl; cout<<"Can be divided."<<endl; }else{ cout<<"Collection #"<<to<<":"<<endl; cout<<"Can't be divided."<<endl; } cout<<endl; } } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator