| ||||||||||
| 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 | |||||||||
小菜 dfs无剪枝#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<set>
#include<vector>
#include<iterator>
#include<map>
using namespace std;
int ji[110],n;
double we[110],sum;
bool c,J[110];
bool dfs(int x,double y)
{
if(y<sum/2.02*1.02 && y>sum/2.02) return true;
if(y>=sum/2.02*1.02) return false;
for(int i=x+1;i<=n;i++)
{
J[ji[i]]=true;
if(dfs(i,y+we[i])) return true;
J[ji[i]]=false;
}
return false;
}
int main()
{
//freopen("in.txt","r",stdin);
int i,j;
while(cin>>n && n)
{
sum=0;
for(i=1;i<=n;i++)
{
cin>>we[i];
sum+=we[i];
ji[i]=i;
}
for(i=2;i<=n && c;i++)
{
c=false;
for(j=2;j<=n-i+2;j++)
{
if(we[i-1]<we[i])
{
swap(we[i-1],we[i]);
swap(ji[i-1],ji[i]);
c=true;
}
}
}
memset(J,false,sizeof(J));
dfs(0,0);
c=false;
for(i=1;i<=n;i++)
{
if(c && !J[i]) cout<<" ";
if(!J[i])
{
cout<<i;
c=true;
}
}
cout<<endl;
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator