ZOJ2898搜索优化

这题暴力复杂度是O(2^n)的，对于24的复杂度明显不可做，我的方法是进行优化，枚举前n/2个，得到每个陷阱对应的宝物编号，这样对应了一个映射，然后枚举剩下的宝物，找到对应陷阱所对应的前半部分宝物，所有宝物的价值之和就是目前的答案，取最大的即可。

宝物和陷阱可以用int和long long压缩，最后放入map中。复杂度O(2^(n/2))

我的代码：

#include <cstring> #include <cstdio> #include <cstdlib> #include <vector> #include <map> #include <algorithm> using namespace std; vector<int> trap[25]; int v[25]; int n,maxd; map<long long,vector<int> > mp; int ret; void run(int st,long long val){ int ans,nst; vector<int> part; if(mp.find(val)==mp.end()) return; part=mp[val]; int m=part.size(); for(int k=0;k<m;k++){ nst=st|part[k]; ans=0; for(int i=0;i<n;i++){ if(nst&(1<<i)){ ans+=v[i]; } } if(ans>ret) ret=ans; } } void dfs(int k,int st,long long val){ int nst; long long nval; if(k==maxd){ if(mp.find(val)==mp.end()){ vector<int> v; v.push_back(st); mp[val]=v; }else{ mp[val].push_back(st); } return; } int m=trap[k].size(); dfs(k+1,st,val); nst=st; nval=0; nst|=(1<<k); for(int i=0;i<m;i++){ nval|=(1ll<<trap[k][i]); } dfs(k+1,nst,val^nval); } void dfs2(int k,int st,long long val){ int nst; long long nval; if(k==n){ run(st,val); return; } int m=trap[k].size(); dfs2(k+1,st,val); nst=st; nval=0; nst|=(1<<k); for(int i=0;i<m;i++){ nval|=(1ll<<trap[k][i]); } dfs2(k+1,nst,val^nval); } int main(){ int m,x; while(~scanf("%d",&n)){ mp.clear(); ret=0; for(int i=0;i<n;i++){ trap[i].clear(); scanf("%d%d",&v[i],&m); for(int j=0;j<m;j++){ scanf("%d",&x); trap[i].push_back(x); } } maxd=n/2; dfs(0,0,0ll); dfs2(maxd,0,0ll); printf("%d/n",ret); } return 0; }