本文主要是介绍UVa 11795 - Mega Man's Mission(状态压缩dp)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
本文出自 http://blog.csdn.net/shuangde800
题目传送门
题意：
你最初只有一个武器，你需要按照一定的顺序消灭n个机器人(n<=16)。每消灭一个机器人将会得到他的武器。
每个武器只能杀死特定的机器人。
问可以消灭所有机器人的顺序方案总数。
思路：
看到了n的规模这么小，就知道可以用状态压缩解决了。
f[s]表示状态为{s}时的方案总数.
我们设{s-1}是s状态把一个二进制位是1的变为0的所有情况，相当于集合中少了某个机器人的所有情况
那么f[s] = sum{ 所有的{s-1}， 消灭了{s-1}个机器人时获得的武器能够杀掉少了的这个机器人}
初始化f[0] = 1, 表示一个机器人都不杀的方案有1个
代码：
/**==========================================* This is a solution for ACM/ICPC problem** @author: shuangde* @blog: blog.csdn.net/shuangde800* @email: zengshuangde@gmail.com*===========================================*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
#include<cstring>
using namespace std;typedef long long int64;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0);const int MAXN = 10010;
int n, maxState;
int p[20];
char str[20];int kill[(1<<16)+10];
int64 f[(1<<16)+10];int main(){int T;int cas = 1;scanf("%d", &T);while(T--){scanf("%d", &n);for(int i=0; i<=n; ++i){scanf("%s", str);p[i] = 0;for(int j=0; str[j]; ++j)if(str[j] == '1')p[i] |= (1<<j);}maxState = (1<<n)-1;kill[0] = p[0];for(int s=1; s<=maxState; ++s){kill[s] = p[0];for(int i=0; i<n; ++i)if((s>>i) & 1) kill[s] |= p[i+1];}memset(f, 0, sizeof(f));f[0] = 1;for(int s=1; s<=maxState; ++s){f[s] = 0;for(int i=0; i<n; ++i)if( (kill[s^(1<<i)]>>i) & 1){f[s] += f[s^(1<<i)];} }printf("Case %d: %lld\n", cas++, f[maxState]);}return 0;
}这篇关于UVa 11795 - Mega Man's Mission(状态压缩dp)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
