UVA 11795 - Mega Man's Mission(状态压缩DP)

  • 内容
  • 评论
  • 相关

很容易想到用d[i][s]表示杀死了i个机器人了, 杀死的机器人集合是s的方法数。

转移也很容易我就不说了, 我的转移复杂度是n^2的, 当然你也可以预处理一下某个机器人能被哪些机器人集合杀死, 直接用位运算与来判断, 使得转移变成O(n)

细节参见代码:

#include <cstdio>  
#include <cstring>  
#include <algorithm>  
#include <iostream>  
#include <string>  
#include <vector>  
#include <stack>  
#include <ctime>  
#include <bitset>  
#include <cstdlib>  
#include <cmath>  
#include <set>  
#include <list>  
#include <deque>  
#include <map>  
#include <queue>  
#define Max(a,b) ((a)>(b)?(a):(b))  
#define Min(a,b) ((a)<(b)?(a):(b))  
using namespace std;  
typedef long long ll;  
typedef long double ld;  
const double eps = 1e-6;  
const double PI = acos(-1);  
const int mod = 1000000000 + 7;  
const int INF = 0x3f3f3f3f;  
const ll INF64 = ll(1e18);  
const int maxn = 17;  
int T,n,m, vis[maxn][1<<maxn], kase = 0, init[maxn], able[maxn][maxn];  
ll d[maxn][1<<maxn];  
ll dp(int i, int s) { // 杀死前i个人,杀死的人的集合为s的方法数  
    ll& ans = d[i][s];  
    if(i == n) return 1LL;  
    if(vis[i][s] == kase) return ans;  
    vis[i][s] = kase;  
    ans = 0;  
    for(int j = 1; j <= n; j++) { // 枚举这次杀死哪个人  
        if(s & (1<<j)) continue;  
        if(init[j]) { // 如果初始武器就能杀死  
            ans += dp(i+1, s | (1<<j));  
        }  
        else {  
            bool ok = false;  
            for(int k = 1; k <= n; k++) {  
                if(s & (1<<k)) {  
                    if(able[k][j]) { ok = true; break; }  
                }  
            }  
            if(ok) ans += dp(i+1, s | (1<<j));  
        }  
    }  
  
    return ans;  
}  
char s[maxn];  
int main() {  
    scanf("%d",&T);  
    while(T--) {  
        scanf("%d", &n);  
        scanf("%s", s+1);  
        for(int j = 1; j <= n; j++) {  
            int cur = s[j]-'0';  
            init[j] = cur;  
        }  
        for(int i = 1; i <= n; i++) {  
            scanf("%s", s+1);  
            for(int j = 1; j <= n; j++) {  
                int cur = s[j] - '0';  
                able[i][j] = cur;  
            }  
        }  
        ++kase;  
        ll ans = dp(0, 0);  
        printf("Case %d: %lld\n", kase, ans);  
    }  
    return 0;  
}  
X
赞助一下:
    支付宝    微信    QQ红包

打开支付宝扫一扫

发表评论

电子邮件地址不会被公开。 必填项已用*标注

00:00 / 00:00
顺序播放