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