传送门:ACM-ICPC 2018 南京赛区网络预赛 E 题
题目大意:
有 $n$ 道题目,Dlsj 已经知道了每一道题的答案,可以直接提交并 AC,每道题的提交时间间隔为 1 分钟,提交题目 $i$ 的得分为 $t×a_i+b_i$,($t$ 为提交时间,$a_i, b_i$已知)。想要提交某道题需要已经 AC 了特定的某几个题,否则不可以提交。例如题目告诉你说,提交第 5 题前,必须要先过了第 2 题和第 6 题,那么想要提交第 5 题,就需要第 2 题、第 6 题已经 AC。可以有些题目不做,因为 $a_i, b_i$ 可能是负数,做了反而分数更低,当然如果有题目不做,那么需要这个题已经 AC 才能提交的题目也做不了。问 Dlsj 能达到的最高分是多少。
解题思路:
因为 $n$ 最大为 20,一道题只有两个状态(已经 AC 了,或者还没做),所以一共最多有 $2^{20}$ 个状态。对于每个状态,我们可以用一个 int 类型的数(二进制)来表示,右数第 i 位为 1 表示题目 $i$ 已经 AC 了,为 0 表示题目 $i$ 还没做。所以我们需要一个大小为 $2^{20}$ 的 int 类型数组,下标值为状态,数据值为到达这个状态时,最多能得多少分,于是题目便可以用 状压DP 来求解了,遍历从 $1$ 到 $2^n$(代码中通常写作 1 << n) 的所有状态,DP 递推就可以了。
通过代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55
| #include <bits/stdc++.h> using namespace std; const int MAXN = 20; struct node { int a, b, pre; } p[MAXN]; int n, si, pi, ans; int mp[1 << MAXN]; int T[1 << MAXN]; bool judge(int i, int j) { for (int k = 1; k <= n; ++k) if ((p[i].pre >> (k - 1)) & 1) if (!((j >> (k - 1)) & 1)) return false; for (int k = 1; k <= n; ++k) { if (k == i) continue; if (j & (1 << (k - 1))) if (p[k].pre & (1 << (i - 1))) return false; } return true; } int main(void) { scanf("%d", &n); for (int i = 1; i <= n; ++i) { scanf("%d%d%d", &p[i].a, &p[i].b, &si); for (int j = 1; j <= si; ++j) { scanf("%d", &pi); p[i].pre |= 1 << (pi - 1); } } for (int i = 1; i < 1 << n; ++i) for (int j = 1; j <= n; ++j) if (i & (1 << (j - 1))) ++T[i]; for (int i = 1; i < 1 << n; ++i) { for (int j = 1; j <= n; ++j) { int ps = 1 << (j - 1); if ((i & ps) && judge(j, i - ps)) mp[i] = max(mp[i], mp[i - ps] + (T[i - ps] + 1) * p[j].a + p[j].b); } ans = max(ans, mp[i]); } printf("%d\n", ans); return 0; }
|