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

发布时间:2017-1-18 9:38:17 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"UVA 11795 - Mega Man's Mission(状态压缩dp)",主要涉及到UVA 11795 - Mega Man's Mission(状态压缩dp)方面的内容,对于UVA 11795 - Mega Man's Mission(状态压缩dp)感兴趣的同学可以参考一下。

B Mega Man’s Missions Input Standard Input Output Standard Output   Mega Man is off to save the world again. His objective is to kill the Robots created by Dr. Wily whose motive is to conquer the world. In each mission, he will try to destroy a particular Robot. Initially, Mega Man is equipped with a weapon, called the “Mega Buster” which can be used to destroy the Robots.  Unfortunately, it may happen that his weapon is not capable of taking down every Robot. However, to his fortune, he is capable of using the weapons from Robots which he has completely destroyed and these weapons maybe able to take down Robots which he otherwise cannot with his own weapon. Note that, each of these enemy Robots carry exactly one weapon themselves for fighting Mega Man.  He is able to take down the Robots in any order as long as he has at least one weapon capable of destroying the Robot at a particular mission. In this problem, given the information about the Robots and their weapons, you will have to determine the number of ways Mega Man can complete his objective of destroying all the Robots.   Input Input starts with an integer T(T≤50), the number of test cases. Each test case starts with an integer N(1≤N≤16). Here N denotes the number of Robots to be destroyed (each Robot is numbered from 1 to N). This line is followed by N+1 lines, each containing N characters. Each character will either be ‘1’ or ‘0’. These lines represent a (N+1)*N matrix. The rows are numbered from 0 to N while the columns are numbered from 1 to N. Row 0 represents the information about the “Mega Buster”. The jth character of Row 0 will be ‘1’ if the “Mega Buster” can destroy the jthRobot. For the remaining N rows, the jth character of ith row will be ‘1’ if the weapon of ith Robot can destroy the jth Robot. Note that, a Robot’s weapon could be used to destroy the Robot itself, but this will have no impact as the Robot must be destroyed anyway for its weapon to be acquired. Output For each case of input, there will be one line of output. It will first contain the case number followed by the number of ways Mega Man can complete his objective. Look at the sample output for exact format.   Sample Input Sample Output 3 1 1 1 2 11 01 10 3 110 011 100 000   Case 1: 1 Case 2: 2 Case 3: 3    题意:给定n代表n个敌人,第一是洛克人的武器,以下n行是n个敌人有的武器,消灭敌人后可以得到她的武器,武器的表示方式是一个二进制数能消灭敌人是1,不能是0,问总共有几种顺序可以消灭所有敌人。 思路:明显的状态压缩DP,先预处理消灭的一些敌人之后拥有的武器可以消灭的敌人数组have,然后dp,dp[i]表示消灭i这个状态的敌人有几种方法,那么推出转移方程为dp[i] = dp[i^(1<<j)] + 1,如果j是可以消灭的敌人。答案最大是16!,注意用long long. 代码: #include <stdio.h> #include <string.h> const int N = 17; const int MAXN = (1<<N); int t, n, s, w[N], have[MAXN]; long long dp[MAXN]; char str[N]; int change(char *str) { int len = strlen(str); int ans = 0; for (int i = 0; i < len; i++) { if (str[i] == '1') ans = (ans|(1<<i)); } return ans; } long long solve() { memset(dp, 0, sizeof(dp)); dp[0] = 1; for (int i = 1; i < (1<<n); i++) { for (int j = 0; j < n; j++) { if (i&(1<<j) && (have[i^(1<<j)]&(1<<j))) dp[i] += dp[i^(1<<j)]; } } return dp[(1<<n) - 1]; } int main() { int cas = 0, i; scanf("%d", &t); while (t--) { scanf("%d", &n); scanf("%s", str); s = change(str); for (i = 0; i < n; i++) { scanf("%s", str); w[i] = change(str); } for (i = 0; i < (1<<n); i++) { have[i] = s; for (int j = 0; j < n; j++) { if (i&(1<<j)) { have[i] = (have[i]|w[j]); } } } printf("Case %d: %lld\n", ++cas, solve()); } return 0; }