题目链接:uva 11795 - Mega Man's Mission
题目大意:给出n,表示有n个敌人,首先给出洛克人的武器(二进制数,表示可以杀死的敌人),然后给出n个敌人的武器,同样是二进制,杀死该敌人后可以获得他的武器,问说一共有多少种击杀顺序。
解题思路:用二进制表示i说那些人被击杀,dp[i]表示这些集合的人被击杀有多少种顺序,然后h[i]表示获得这些人的武器后可以击杀其他多少人。
#include <stdio.h>
#include <string.h>
typedef long long ll;
const int N = 17;
const int M = 1<<N;
int n, g[N], h[M];
ll dp[M];
int get() {
char str[M];
scanf("%s", str);
int len = strlen(str), ans = 0;
for (int i = 0; i < len; i++) if (str[i] == '1')
ans |= (1<<i);
return ans;
}
void init () {
scanf("%d", &n);
h[0] = get();
for (int i = 0; i < n; i++) g[i] = get();
for (int i = 0; i < (1<<n); i++) {
h[i] = h[0];
for (int j = 0; j < n; j++) if (i & (1<<j)) {
h[i] |= g[j];
}
}
}
ll solve() {
dp[0] = 1;
for (int i = 1; i < (1<<n); i++) {
dp[i] = 0;
for (int j = 0; j < n; j++) if (i&(1<<j) && h[i^(1<<j)]&(1<<j))
dp[i] += dp[i^(1<<j)];
}
return dp[(1<<n)-1];
}
int main () {
int cas;
scanf("%d", &cas);
for (int i = 1; i <= cas; i++) {
init();
printf("Case %d: %lld\n", i, solve());
}
return 0;
}
分享到:
相关推荐
富士电机FRENIC-MEGA 变频器使用说明书
LSI 阵列卡windo系统管理软件,Windows_LSI-MegaRAID_Storage_Manager LSI 阵列卡windo系统管理软件,Windows_LSI-MegaRAID_Storage_Manager LSI 阵列卡windo系统管理软件,Windows_LSI-MegaRAID_Storage_Manager ...
洛克人时间的齿轮
FUJI-富士 高性能多功能变频器FRENIC-MEGA系列样本zip,FUJI-富士 高性能多功能变频器FRENIC-MEGA系列样本
变频器说明书大全系列-FRN-MEGA(G1S).rar
富士FRENIC-MEGA系列样本.rar,富士FRENIC-MEGA系列样本.
富士_高性能多功能变FRENIC-MEGA Lite系列样本.pdfpdf,富士_高性能多功能变FRENIC-MEGA Lite系列样本 1、具备业界最高水平的控制性能 1).对应带速度传感器矢量控制、无速度传感器矢量控制(动态转矩矢量控制)、V/f...
arduino-mega2560的设计文件,SCH和PCB软件为Eagle
Protues仿真实例-MEGA16-EEPROM.rar
基于AT-mega88的红外触摸屏设计,基于AT-mega88的红外触摸屏设计
atmega16u2-Mega2560固件 烧录用的 可用于UNO 328P MEGA2560等开发板
官方离线安装包,亲测可用
单片机-mega_megaDXP资料.zip
arduino-mega2560_R3硬件原理图+PCB文件,可以做为你的学习设计参考。
elecfans.com-MEGA128系统板PCB电路原理图(1)
AVR-STM32-Arduino-Mega2560 (3).pdsprj
Knutwurst的i3 MEGA(M / S / P / X)固件(基于Marlin 2.0.x) (毕特GENUR DURCHLESEN!/请仔细阅读!) 温恩·迪尔·盖菲尔特(Wenn dirgefällt),是马赫(Kanst du mir hier einen)的玛菲(Kaffest * Es ...
arduino-mega-schematic.rar
变频器说明书系列-FRN-MEGA.pdf
程序包含三首曲子,采用C语言编写,使用的是AT-MEGA16单片机。