这真的是橙题吗
题解
读题,每个材料都有用或不用两种选择,然后n的数据范围也很小,所以考虑二进制dp (别管我为什么不叫状态压缩)
遍历 0 到 \(2^{20}-1\)(十进制下),如果存在互相矛盾的1,代表这个状态不能用
code
#include<bits/stdc++.h>
using namespace std;
int n,m;
map<int,map<int,int> > q;
int check(int now)
{
vector<int> food;
for(int i=0;i<n;i++)
{
if((now>>i)&1) food.push_back(i+1);
}
for(int i=0;i<food.size();i++)
{
for(int j=i+1;j<food.size();j++)
{
if(q[food[i]][food[j]]) return 0;
}
}
return 1;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int x,y;
cin>>x>>y;
q[x][y]=q[y][x]=1;
}
int ans=0;
for(int i=0;i<(1<<n);i++) if(check(i)) ans++;
cout<<ans<<endl;
return 0;
}
题解2,据说二进制dp等于爆搜??
爆搜,搜索深度代表第 \(i\) 个材料要不要用,如果前面没有出现矛盾代表能用
code
#include<bits/stdc++.h>
using namespace std;
int n,m;
int ans=0;
int para[25]={0};
void dfs(int who,int now)//now中,0代表可以选,1代表选过了或者无法选
{
if(who==n+1){ans++;return;}
dfs(who+1,now);//代表不选当前材料
if(!((1<<who)&now)) dfs(who+1,now|para[who]);
//为什么这里要判断who能不能选而不是para符不符合?因为二进制dp只能表示两种状态,选了和没法选是不一样的,因此我们统一把1变成无法选,0代表可以选
//这样一来只需要判断能不能选就行了
}
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int x,y;
cin>>x>>y;
para[x]|=(1<<y);
para[y]|=(1<<x);
}
for(int i=1;i<=n;i++) para[i]|=(1<<i);
dfs(1,0);
cout<<ans;
return 0;
}
标签:now,int,题解,P7859,who,代表,ans,GEPPETTO,2016
From: https://www.cnblogs.com/pure4knowledge/p/18115681