有 \(n\) 道题目，每道题分为小题目和大题目，只有做完了小题目才能做大题目，提交结果会在比赛结束后得知。其中，做第 \(i\) 个小题目需要 \(ScoreSmall_i\) 分钟，可以获得得分 \(TimeSmall_i\) ；做第 \(i\) 个大题目需要 \(ScoreLarge_i\) 分钟，可以获得得分 \(TimeLarge_i\) 。每个小题目可以一遍过，第 \(i\) 个大题目有 \(ProbFail_i\) 的几率错误，总罚时是 最后一次正确提交的时间。现在你有 \(t\) 分钟，求在这 \(t\) 分钟内你最多期望能够获得多少分，并且在满足得分最多的情况下使得罚时最小。
\(n\leq1000;t,\ TimeSmall_i,\ TimeLarge_i\in[1,\ 1560];\ ScoreSmall_i,\ ScoreLarge_i\in[1,\ 10^9];\ 0\leq ProbFail_i\leq 1\)
dp，贪心，概率
背包可以解决最高得分，那么现在要找到一种最优的顺序使得罚时最低。
可以发现 \(Small\) 对罚时没有特殊影响，可以直接计算。假设需要解决两道题 \(i,\ j\) 的 \(Large\) ，令 \(t_i=TimeLarge_i,\ p_i=ProbFail_i\)，若 \(i\) 排在 \(j\) 之前，罚时为 \((1-p_j)(t_i+t_j)+t_i(1-p_i)p_j\)
化式子得，若 \(i\) 排在 \(j\) 之前的得分大于 \(j\) 排在 \(i\) 之前当且仅当 \(t_i\times p_i/(1-p_i)>t_j\times p_j/(1-p_j)\)
按照这个规则排序即可。
代码
#includeusing namespace std;typedef long double db;const db eps = 1e-15;const int maxn = 2010;int n, m;db dp[maxn], val[maxn];struct node { int v1, v2, t1, t2; db p; inline bool operator < (const node &o) const { return t2 * p / (1 - p) < o.t2 * o.p / (1 - o.p); }} a[maxn];int main() { scanf("%d %d", &n, &m); for (int i = 1; i <= n; i++) { double f; scanf("%d %d %d %d %lf", &a[i].v1, &a[i].v2, &a[i].t1, &a[i].t2, &f); a[i].p = f; } sort(a + 1, a + n + 1); for (int i = 1; i <= m; i++) { dp[i] = -1e18, val[i] = 1e18; } for (int i = 1; i <= n; i++) { db p = a[i].p, tmp1, tmp2; int v1 = a[i].v1, v2 = a[i].v2; int t1 = a[i].t1, t2 = a[i].t2; for (int j = m; j >= t1; j--) { tmp1 = dp[j - t1] + v1, tmp2 = val[j - t1] + t1; if (dp[j] < tmp1 || (fabs(dp[j] - tmp1) < eps && val[j] > tmp2)) { dp[j] = tmp1, val[j] = tmp2; } if (j < t1 + t2) continue; tmp2 = dp[j - t1 - t2] + v1 + (1 - p) * v2; tmp1 = t1 + (1 - p) * (j - t1) + p * val[j - t1 - t2]; if (dp[j] < tmp2 || (fabs(dp[j] - tmp2) < eps && val[j] > tmp1)) { dp[j] = tmp2, val[j] = tmp1; } } } int pos = 0; for (int i = 1; i <= m; i++) { if (dp[pos] < dp[i] || (fabs(dp[pos] - dp[i]) < eps && val[i] < val[pos])) { pos = i; } } printf("%.10lf %.10lf", (double) dp[pos], (double) val[pos]); return 0;}