Input
The input has several test cases, each starts with n (2 <= n <= 16), the number of programs. The following n lines contain the name of the program and its priority, with each program on a line. The name is a string of no more than 10 characters. The priority is an integer from 1 to 100. The next line contains a single integer m (0 <= m <= 1,024), which is the length of the list of the conflicting programs. The following m lines each contains several names of the programs which cannot run together.
The input is terminated with a case n = 0. This case should not be processed.
Output
Print the case number and the maximal total priority value you can get on a line. Adhere to the sample output format.
Sample Input
3 HARDDISK 20 FLOPPY 10 CDROM 15 1 CDROM HARDDISK 5 HARDDISK 20 FLOPPY 10 CDROM 15 SERIAL 25 MOUSE 20 3 CDROM HARDDISK FLOPPY FLOPPY SERIAL SERIAL MOUSE 0
Sample Output
System 1: 30 System 2: 60
题意:先给出n个任务和每个任务的价值,然后给出m个限制条件,每个限制条件包括一些任务,说明这些任务不能同时进行处理。求能同时处理的任务的最大价值是多少。
分析:因为n不大于16,而且限制条件也比较少,所以很容易想到状态压缩。
先把那些限制条件转化为一个10进制整数,它的二进制形式中的1表示这些任务不能同时处理;然后从0开始枚举状态,判断当前状态与限制条件是否冲突,如果不冲突,算出当前状态的价值总和,与最大值进行比较即可。
注意:任务的名称不一定全是字母,可能由其他字符组成,我就是因为这里WA了还找不到错误。
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<string> #include<cstdlib> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #include<algorithm> using namespace std; typedef long long LL; map<string, int> mp; vector<int> v[1030]; int a[30]; int sta[1030]; int pro[17] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536}; int main() { int n, m, i, j, cas = 0; string str, tmp; int val; while(cin >> n && n) { mp.clear(); for(i = 1; i <= n; i++) { cin >> str >> val; mp[str] = i; a[i] = val; } memset(v, 0, sizeof(v)); memset(sta, 0, sizeof(sta)); cin >> m; getchar(); for(int k = 0; k < m; k++) { getline(cin, str); int len = str.length(); tmp = ""; for(i = 0; i < len; i++) { if(str[i] != ' ' && str[i] != '\0') //注意此处的判断条件 tmp += str[i]; else { v[k].push_back(mp[tmp]); tmp = ""; } } v[k].push_back(mp[tmp]); sort(v[k].begin(), v[k].end()); for(int j = 0; j < v[k].size(); j++) sta[k] += pro[n-v[k][j]]; } int maxn = 1; for(i = 1; i <= n; i++) maxn *= 2; int ans = 0; for(int i = 0; i < maxn; i++) { int flag = 1; for(j = 0; j < m; j++) { if((i & sta[j]) == sta[j]) { flag = 0; break; } } if(flag) { int tmp_sum = 0; int tt = 0, temp = i; while(temp) { if(temp % 2 == 1) tmp_sum += a[n-tt]; tt++; temp /= 2; } ans = max(ans, tmp_sum); } } printf("System %d: %d\n", ++cas, ans); } return 0; }
ZOJ 1639 Hang Up the System (状态压缩),布布扣,bubuko.com
ZOJ 1639 Hang Up the System (状态压缩)
原文:http://blog.csdn.net/lyhvoyage/article/details/38350027