Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

小菜 dfs无剪枝

Posted by dlndxd at 2015-09-29 15:55:06 on Problem 1853
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator