洛谷P10143 [WC2024] 代码堵塞题解

题目链接：P10143 [WC2024] 代码堵塞

题意：

小 $\beth$ 为了纪念停办的 codejam，准备了一场“代码堵塞纪念赛”。小 $\beth$ 的朋友小 $\mho$ 也来围观，于是小 $\beth$ 想预测小 $\mho$ 的成绩。

比赛共 $T$ 秒，有 $n$ 道题。第 $i(1 \le i \le n)$ 题分数为 $a_i$，小 $\beth$ 预测小 $\mho$ 需要 $t_i$ 秒完成。

题目有两种类型：结果可见和结果不可见。结果不可见的题在比赛结束后才能知道评测结果，而结果可见的题在提交后立即得到评测结果。小 $\beth$ 还没确定每道题的类型。

小 $\mho$ 由于从不写对拍，所以会先按编号从小到大完成所有结果可见的题，再按编号从小到大完成所有结果不可见的题。小 $\mho$ 会花 $t_i$ 秒完成第 $i$ 题，当小 $\mho$ 花费在第 $i$ 题和在第 $i$ 题之前完成的所有题的时间总和不超过 $T$，就会在第 $i$ 题产生提交。

由于小 $\mho$ 提交即 AC，所以小 $\beth$ 想知道对于所有 $2^n$ 种确定 $n$ 道题类型的方案，小 $\mho$ 所能得到的分数总和的和。由于答案很大，你需要将答案对 $998244353$ 取模。

输入格式：

输入的第一行包含三个整数 $c, n, T$，表示测试点编号，题数和比赛时间。样例中的 $c$ 表示其满足的限制条件与第 $c$ 个测试点一致。

输入的第二行包含 $n$ 个整数 $a_1, a_2, \cdots , a_n$，分别表示每道题的分数。

输入的第三行包含 $n$ 个整数 $t_1, t_2, \cdots , t_n$，分别表示小 $\mho$ 做每道题的时间。

输出格式：

输出一行包含一个整数，表示对于所有确定 $n$ 道题类型的方案，小 $\mho$ 所能得到的分数总和的和，对 $998244353$ 取模。

数据范围：

对于所有测试数据：

$1\le n\le 200$，

$1\le T\le 3\times 10^5$，

$\forall 1\le i\le n , 1\le a_i\le 3\times 10^5$，

$\forall 1\le i\le n, 1\le t_i\le T$。

设 $f_{i,j}$ 为考虑到 $i$ ，时间花费为 $j$ 的方案数。考虑第 $i$ 道题。

如果 $i$ 结果可见，小于 $i$ 的可能在第 $i$ 道前提交，大于 $i$ 的不可能在 $i$ 前提交。

前者实际上为dp统计的方案数，后者只需要乘一个 $2^{n-i}$ 。

如果 $i$ 结果不可见，小于 $i$ 的一定在 $i$ 前提交，大于 $i$ 的可能在 $i$ 后提交。

这与刚才的情况恰好相反，于是我们倒着做一遍dp即可

时间复杂度 $\mathcal{O}(nT)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int P = 998244353;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
void add(int &x, int y) { (x += y) >= P ? x -= P : 0; }
#define N ((int)(215))
#define M ((int)(3e5 + 15))

int pw[N],a[N],t[N],s[N],dp[M];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int _, n, T; cin >> _ >> n >> T; pw[0] = 1;
    for(int i = 1; i <= n; i++) pw[i] = pw[i - 1] * 2 % P;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) { cin >> t[i], s[i] = s[i - 1] + t[i]; }
    int res = 0; dp[0] = 1;
    for(int i = 1; i <= n; i++)
    {
        int sum = 0;
        for(int j = 0; j + t[i] <= T; j++) add(sum, dp[j]);
        add(res, a[i] * sum % P * pw[n - i] % P);
        for(int j = T; j >= t[i]; j--) add(dp[j], dp[j - t[i]]);
    }
    memset(dp, 0, sizeof(dp)); dp[0] = 1;
    for(int i = n; i; i--)
    {
        int sum = 0;
        for(int j = 0; j + t[i] + s[i - 1] <= T; j++) add(sum, dp[j]);
        add(res, a[i] * sum % P * pw[i - 1] % P);
        for(int j = T; j >= t[i]; j--) add(dp[j], dp[j - t[i]]);
    }
    cout << res << '\n';
    return 0;
}