PKU 2356 Find a multiple
http://poj.org/problem?id=2356
n個の数字から1個以上の数字を選んでその和がnの倍数になるようにしろというような問題。
枝刈りdfsしました。
n=100000くらいの似たような問題だとTLEして通らないのが悲しいです。
int ans[20000]; int sz; int n; int in[10000]; int vis[10000]; bool dfs(int ne,int v){ //cout<<ne<<' '<<v<<endl; if(ne && !v)return true; if(v)vis[v]=ne; for(int i=ne;i<n;++i){ if(vis[(v+in[i])%n]!=-1 && vis[(v+in[i])%n]<=i)continue; if(dfs(i+1,(v+in[i])%n)){ ans[sz++]=in[i]; return true; } } return false; } main(){ cin>>n; rep(i,n)cin>>in[i]; memset(vis,-1,sizeof(vis)); dfs(0,0); cout<<sz<<endl; rep(i,sz)cout<<ans[i]<<endl; }