| ||||||||||
| 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