#12. 先写暴力，再写正解

· · 题解

假设一场考试的时间为 T，有 n 道题，每题有 a_i 暴力分，需要 s_i 的时间，有额外 b_i 分是正解，需要在写完暴力的前提下多花 t_i 的时间，但有 p_i 的概率写挂。问最大期望得分以及最大期望得分情况下的最小期望罚时。罚时定义为最后一次成功提交的时间。

下面设 p_i 代表有 p_i 的概率写对。

假设写正解不需要额外的时间，只是有概率写挂，或者说罚时的定义为最后一次任意的提交。那么显然每道题只有三种决策：不写，写暴力，写正解。容易使用 01 背包做到 O(nT)。

现在考虑假设目前已经有了某种决策，假设暴力和正解交替选，那么就算所有都没写挂，时间也要那么多。还不如先写暴力，最后写正解，这样只要写挂了就不用算罚时了！考虑正解之间的顺序问题，如果我们可以钦定这个位置关系，那么就可以愉快的背包啦！

考虑 exchange argument。对于相邻的 i,j，当 i 在 j 前面时，罚时的期望是 p_j(t_j+t_i)+(1-p_j)p_it_i，j 在 i 前同理即为 p_i(t_i+t_j)+(1-p_i)p_jt_j。当 p_j(t_j+t_i)+(1-p_j)p_it_i<p_i(t_i+t_j)+(1-p_i)p_jt_j 即 \frac{(1-p_i)t_i}{p_i}<\frac{(1-p_j)t_j}{p_j} 时 i 在 j 前更优，按这个排序即可。

背包部分的转移如下：

f_{i-1,j}\to f_{i,j}\\ f_{i-1,j-s_i}+a_i\to f_{i,j}\\ f_{i-1,j-s_i-t_i}+a_i+p_ib_i\to f_{i,j}\\

同时记录 g 代表最小期望时间，在最大期望得分相同时如下更新 g：

g_{i-1,j}\to g_{i,j}\\ g_{i-1,j-s_i}+s_i\to g_{i,j}\\ (g_{i-1,j-s_i-t_i}+s_i)(1-p_i)+p_i\times j\\ 
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e3;
template<typename T>
inline void read(T &x)
{
    T sgn = 1;
    char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') sgn = -1;
    for (x = 0; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
    x *= sgn;
}
struct node{
    int a, b, s, t;
    __float128 p;
}q[maxn];
int n, T;
__float128 f[maxn], g[maxn];
bool cmp(node x, node y) { return (1 - x.p) * x.t / x.p < (1 - y.p) * y.t / y.p; }
int main()
{
    read(n); read(T); long double tmp;
    for (int i = 1; i <= n; i++) read(q[i].a), read(q[i].b), read(q[i].s), read(q[i].t), scanf("%Lf", &tmp), q[i].p = 1 - tmp;
    sort(q + 1, q + n + 1, cmp);
    memset(g, 0x3f, sizeof(g));
    f[0] = 0, g[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = T; j >= q[i].s; j--)
        {
            if (f[j - q[i].s] + q[i].a > f[j])
            {
                f[j] = f[j - q[i].s] + q[i].a;
                g[j] = g[j - q[i].s] + q[i].s;
            }
            else if (f[j - q[i].s] + q[i].a == f[j]) g[j] = min(g[j], g[j - q[i].s] + q[i].s);
            if (j >= q[i].s + q[i].t)
            {
                if (f[j - q[i].s - q[i].t] + q[i].a + q[i].p * q[i].b > f[j])
                {
                    f[j] = f[j - q[i].s - q[i].t] + q[i].a + q[i].p * q[i].b;
                    g[j] = (1 - q[i].p) * (g[j - q[i].s - q[i].t] + q[i].s) + q[i].p * j;
                }
                else if (f[j - q[i].s - q[i].t] + q[i].a + q[i].p * q[i].b == f[j]) g[j] = min((1 - q[i].p) * (g[j - q[i].s - q[i].t] + q[i].s) + q[i].p * j, g[j]);
            }
        }
    }
    __float128 ans1 = 0, ans2 = 1e18;
    for (int j = 0; j <= T; j++)
    {
        if (ans1 < f[j])
        {
            ans1 = f[j];
            ans2 = g[j];
        }
        else ans2 = min(ans2, g[j]);
    }
    printf("%.10Lf %.10Lf\n", (long double)ans1, (long double)ans2);
    return 0;
}

如果对题目进行一些修改，比如说不一定要写暴力再写正解。但其实这可以理解为写了 0 分钟的暴力，所以本质上是一样的。