首页 > 代码库 > uva10817 - Headmaster's Headache(01背包)
uva10817 - Headmaster's Headache(01背包)
题目:uva10817 - Headmaster‘s Headache(01背包)
题目大意:这间学校开设S门棵,给出校长已经有的师资(n),然后再给吃m个应聘者,给出的师资和应聘者都会给出雇佣他们需要的钱还有他们会教的科目。要使得每门课都至少要有两个老师教,然后从应聘者中挑选人,要求雇佣费用最少,注意之前的请的老师也是要算进去的。
解题思路:01背包,每个应聘者要不雇用,要不就不雇佣,然后这个有8门课,用16位表示,第i门课有一个老师教的话,就在2进制的i位上放上1,如果有两个老师,就在i + s上放上1.
例如4门课都只有一个老师教的话:00001111 如果都有两位老师教的话11110000.细节注意。
代码:
#include <cstdio> #include <cstring> const int INF = 0x3f3f3f3f; const int N = 105; const int M = 8; const int maxn = 1<<(2 * M); int s, m, n; int T[N][M]; int num[N]; int cost[N]; int dp[maxn][N]; int v[M + 1]; int mm, sum; int Min (const int a, const int b) { return a < b? a: b;} void init (int st) { for (int i = st; i < mm; i++) for (int j = 1; j <= n + 1; j++) dp[i][j] = INF; for (int i = 1; i <= n + 1; i++) dp[mm][i] = 0; } int DP (int st, int k) { int& ans = dp[st][k]; if (ans != INF) return ans; if (k <= n) { int newst = st; for (int j = 0; j < num[k]; j++) { if (newst & (1 << (T[k][j] - 1))) { newst |= (1 << (T[k][j] - 1 + s)); newst &= ~(1 << (T[k][j] - 1)); } else if (!(newst & (1 << (s + T[k][j] - 1)))) newst |= (1 << (T[k][j] - 1)); } // printf ("%d %d\n", st , newst); ans = Min (ans, Min (DP(newst, k + 1) + cost[k], DP(st, k + 1))); } if (ans == INF) ans = INF + 1; return ans; } int main () { int st; int money, t; char ch; while (scanf ("%d%d%d", &s, &m, &n), s || m || n) { st = sum = 0; memset (v, 0, sizeof (v)); for (int i = 1; i <= m; i++) { scanf ("%d", &money); sum += money; while (scanf ("%c", &ch)) { if (ch == '\n') break; if (ch >= '1' && ch <= '8') { if (v[ch - '0'] < 2) { v[ch - '0']++; } } } } for (int i = 1; i <= n; i++) { scanf ("%d", &cost[i]); t = 0; while (scanf ("%c", &ch)) { if (ch == '\n') break; if (ch >= '1' && ch <= '8') { T[i][t++] = ch - '0'; } } num[i] = t; } for (int i = 1; i <= s; i++) if (v[i]) st += 1 << (i - 1 + (v[i] - 1) * s); mm = (1<<(2 * s)) - (1<<s); init (st); printf ("%d\n", DP(st, 1) + sum); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。