UVA 10817 Headmaster's Headache——dp

UVA 10817 Headmaster's Headache——dp

刷表状压，没什么特别的

#include #include #include #include using namespace std;const int INF = 0x3f3f3f3f;const int maxn = (1<<16)+10;int s, m, n;struct A { int cost, cnt, c[10]; }a[110];int dp[110][maxn];void add(int &state, int x) { if (state & (1<<(x-1))) state |= (1<<(x+s-1)); else state |= (1<<(x-1));}int main() { //freopen("out.txt", "w", stdout); while (~scanf("%d %d %d", &s, &m, &n) && s) { char t; int cost, c, sumcost = 0, sumc = 0; for (int i = 1; i <= m; i++) { scanf("%d", &cost); sumcost += cost; while (~scanf("%c", &t) && t != '\n') { scanf("%d", &c); add(sumc, c); } } for (int i = 1; i <= n; i++) { scanf("%d", &a[i].cost); int &cnt = a[i]-t; cnt = 0; while (~scanf("%c", &t) && t != '\n') { scanf("%d", &c); a[i].c[++cnt] = c; } } memset(dp, INF, sizeof(dp)); dp[0][sumc] = sumcost; for (int i = 1; i <= n; i++) { for (int j = 0; j < (1<<(2*s)); j++) { if (dp[i-1][j] >= INF) continue; sumc = j; for (int k = 1; k <= a[i]-t; k++) add(sumc, a[i].c[k]); dp[i][j] = min(dp[i][j], dp[i-1][j]); dp[i][sumc] = min(dp[i][sumc], dp[i-1][j] + a[i].cost); } } printf("%d\n", dp[n][(1<<(2*s))-1]); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。