题解：P10303 [THUWC 2020] 报告顺序

LittleAcbg · 2026-03-06 20:03:53 · 题解

很容易想到状压 DP，维护听了某一部分报告后，兴奋度的最大正值、最小正值、最大负值和最小负值。

但写完后发现挂了 #40 这个点，这是因为上述做法本身就有问题。注意到 f(x)=a\vert x\vert+bx+c 这个函数存在额外的零点，正负会出现问题，所以我们需要把可能构成零点的值也讨论了。

不过我们不需要维护零点，因为函数的定义域是整数集，而当 \vert x\vert>L=225 时，它经过 n\le15 次操作，每次绝对值至多减 \vert c\vert_{\max}=15，因此它一定不可能构成零点。当然也可能将 f(x) 展开成 c+(b\pm a)x 后 x 前系数为 0，不过这时任意同符号数均会得到一样的结果，无需讨论。

于是我们就得出了算法：增加一个数组维护听了某一部分报告后兴奋度恰好等于 x 的可行性。值域取 [-L,L],L=225 即可。

时间复杂度 O(2^nnL)，记得开 __int128。

:::success[参考代码]

删去了快读快写部分。

using ll = __int128_t;
const int N = 15;
const int P = 32768;
const int M = 451;
const int T = 225;
const ll INF = 1e30;
int n,s,a[N],b[N],c[N];
ll pmx[P],pmn[P],nmx[P],nmn[P];
struct {
    bool _[M];
    inline bool&operator[](const int&p) {return _[p + T];}
} f[P];
void upd(int p, ll s)
{
    if (s > 0)
    {
        chkmx(pmx[p], s);
        chkmn(pmn[p], s);
    }
    else if (s < 0)
    {
        chkmx(nmx[p], s);
        chkmn(nmn[p], s);
    }
    if (-T <= s && s <= T) f[p][s] = 1;
}
int main()
{
    cin >> n >> s;
    for (int i = 0; i < n; ++i) cin >> a[i] >> b[i] >> c[i];
    int nPtn = (1 << n);
    fill(pmn, pmn + nPtn, INF);
    fill(nmx, nmx + nPtn, -INF);
    upd(0, s);
    for (int p = 1; p < nPtn; ++p) for (int i = 0; i < n; ++i) if (p >> i & 1)
    {
        int q = (p ^ (1 << i));
        if (pmx[q]) upd(p, (a[i] + b[i]) * pmx[q] + c[i]);
        if (pmn[q] < INF) upd(p, (a[i] + b[i]) * pmn[q] + c[i]);
        if (nmx[q] > -INF) upd(p, (b[i] - a[i]) * nmx[q] + c[i]);
        if (nmn[q]) upd(p, (b[i] - a[i]) * nmn[q] + c[i]);
        for (int s = -T; s <= T; ++s) if (f[q][s]) upd(p, a[i] * abs(s) + b[i] * s + c[i]);
    }
    cout << (pmx[nPtn - 1] ? pmx[nPtn - 1] : f[nPtn - 1][0] ? 0 : nmx[nPtn - 1]) << endl;
    return 0;
}

:::