|
题解： 定义消灭到s状态为以s的二进制为1处表示的行全都被消灭。 由于n的大小，想到状态压缩的方法。 用st表示，已经消灭到s状态后可以消灭的所有敌人。 用dp表示，消灭到s状态时，有多少种方法。 解法1）我们可以假设最后消灭的一个元素为j，则 j 要满足的条件是：（(1 << j ) & s ) && ( st[i ^ ( 1 << j ) ] & ( 1 << j ) ) 当前状态已经消灭j，同时，在未消灭j之前可以消灭j 则 dp[ i ] += dp[ i ^ ( 1 << j ) ] ;//当前状态加上未消灭j的状态。 解法2）我们假设下一个要消灭的敌人为j，则j要满足的条件为：（！（(1 << j ) & s） ) && ( st[ i ] & ( 1 << j ) ) 当前状态未消灭j，同时，在当前状态可以消灭j 则 dp[ i | ( 1 << j ) ] += dp[ i ]
注：st表示的状态如：110应记为3，不能记为6.（要与敌人的序号对应啊） 解法1代码如下：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
string str[20];
ll s[20];
ll st[1<<17];
ll dp[1<<17];
void str_to_ll(ll i){
for(ll t = 0;t<str.length();t++){
if(str[t] == '1')
s |= 1<<t;
}
}
int main(){
ll T;
ll ca = 1;
cin>>T;
while(T--){
ll n;
cin>>n;
memset(s,0,sizeof(s));
memset(st,0,sizeof(st));
memset(dp,0,sizeof(dp));
for(ll i = 0;i<=n;i++){
cin>>str;
str_to_ll(i);
}
st[0] = s[0];
for(ll i = 0;i<(1<<n);i++){
st = st[0];
for(ll j = 0;j<n;j++){
if((1<<j)&i)
st|=s[j+1];
}
}
// for(ll i = 0;i<(1<<n);i++){
// cout<<st<<" "<<i<<endl;
// }
dp[0] = 1;
for(ll i = 1;i<(1<<n);i++){
dp = 0;
for(ll j = 0;j<n;j++){
if(((1<<j)&i)&&(st[i^(1<<j)]&(1<<j))){
dp += dp[i^(1<<j)];
}
}
}
// for(ll i = 0;i<(1<<n);i++){
// cout<<dp<<" "<<i<<endl;
// }
cout<<"Case "<<ca++<<": ";
cout<<dp[(1<<n)-1]<<endl;
}
}
| 
收藏
淘帖
踩
