UVa 10817 Headmaster's Headach(状態圧縮DP)

タイトル:
ある学校は先生を招聘したいと思って、各学科に2人以上の先生が授業をして、しかも総費用を最小限に抑えることを要求します.S(最大8個)学科、現職のM(最大20個)先生(引き続き招聘しなければならない)、N(最大100個)部申請があります.その後のM行には少なくとも2つの整数があり、現職の先生の給料と教授の授業(1つだけではないかもしれません)を表しています.さらにその後のN行には、少なくとも2つの整数がこの先生を招聘するのに必要な費用と、彼が教授した授業(1つだけではないかもしれません)を表しています.
考え方:
http://www.cnblogs.com/staginner/archive/2011/12/07/2278727.html
状態圧縮をどのように行うかが重要であり,リンクの構想は細かく考えなければならない.

#include <cstdio> #include <cstdlib> #include <cstring> #include <climits> #include <cctype> #include <algorithm>

using namespace std; const int MAXD = 10000; const int MAXN = 110; int s, m, n; int dp[MAXN][MAXD]; int need[12], tech[MAXN][12], state[12]; int cost[MAXN]; void solve() { for (int i = 1; i <= s; ++i) need[i] = 2; char b[100]; int v = 0; for (int i = 0; i < m; ++i) { gets(b); int k = strlen(b); int t; sscanf(b, "%d", &t); v += t; int j = 0; while (isdigit(b[j])) ++j; for (++j; j < k; ++j) { sscanf(&b[j], "%d", &t); if (need[t]) --need[t]; while (isdigit(b[j])) ++j; } } memset(tech, 0, sizeof(tech)); for (int i = 1; i <= n; ++i) { gets(b); int k = strlen(b); int t; sscanf(b, "%d", &t); cost[i] = t; int j = 0; while (isdigit(b[j])) ++j; for (++j; j < k; ++j) { sscanf(&b[j], "%d", &t); tech[i][t] = 1; while (isdigit(b[j])) ++j; } } memset(dp, 0x3f, sizeof(dp)); int P = 0; for (int i = 1; i <= s; ++i) P = 3 * P + 2; for (int i = 0; i <= P; ++i) { int t = i; for (int j = 1; j <= s; ++j) state[j] = t % 3, t /= 3; int j; for (j = 1; j <= s && state[j] >= need[j]; ++j); if (j == s + 1) dp[0][i] = v; } for (int i = 1; i <= n; ++i) { for (int j = 0; j <= P; ++j) { int t = j; for (int k = 1; k <= s; ++k) state[k] = t % 3, t /= 3; for (int k = 1; k <= s; ++k) if (tech[i][k] && state[k] < 2) ++state[k]; t = 0; for (int k = s; k >= 1; --k) t = 3 * t + state[k]; dp[i][j] = min(dp[i-1][j], dp[i-1][t] + cost[i]); } } } int main() { char b[100]; while (gets(b)) { sscanf(b, "%d %d %d", &s, &m, &n); if (!s) break; solve(); printf("%d
", dp[n][0]); } return 0; }