本文最后更新于:2020年4月11日 下午

要获得完美的成绩,您几乎必须回答查询。 因此,如果 不使用第i个项而选择$ans [i] [j] = j $,则只需使用给定的$k$和$x$引用$ans [k] [mx]$即可获得答案。

首先,找到重复的组合。

结果是
$dp [i] [j] = dp [i] [j-1] + dp [i-1] [j] -dp [i-1] [jai-1]$

至此,我将像往常一样要求它。

将其设置为“返回”形式(即,通过引用i +1查找i +1)。

它只是改变公式。在涉及i的所有部分上加1,调整两侧,并将其转换为“ dp [i] [j] =”的形式,然后
dp [i] [j] = dp [i + 1] [j] -dp
它变为[i +1] [j-1] + dp [i] [j-ai-1]

现在,重要的是项目的顺序与之无关。

换句话说,现在
dp [i] [j] =从项中选择
第i个项到第i个项的方式的数量。您可以找到未考虑的选择数量。

所以选择一个总I + 1的,取代要排除数量i,
而不选择[i] [j]

可以得到,
ANS [ i] [j] = dp [n] [j] -dp [n] [j-1] + ans [i] [j-ai-1]

之后,如果您循环i和j并执行第二次DP,则可以使用回答每个查询。

核心部分伪代码

const int MOD = 1e9+7;
int dp[111][111];
int dpSum[111];
 
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M, Q;
    cin >> N >> M >> Q;
    if (N > 100 || M > 100 || Q > 100) return 0;
    vector<int> a(N);
    for (int i = 0; i < N; i++) cin >> a[i];
    while (Q--) {
        int k, x;
        cin >> k >> x;
        k--;
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1;
        int m = M-x;
        for (int i = 0; i < N; i++) {
            if (i == k) {
                for (int j = 0; j <= m; j++) {
                    dp[i+1][j] = dp[i][j];
                }
                continue;
            }
            for (int j = 0; j <= m; j++) dpSum[j+1] = (dpSum[j] + dp[i][j]) % MOD;
            for (int j = 0; j <= m; j++) {
                dp[i+1][j] = dpSum[j+1] - dpSum[max(0, j-a[i])];
                dp[i+1][j] = (dp[i+1][j]+MOD)%MOD;
            }
        }
        cout << dp[N][m] << endl;
    }
    return 0;
}

本文在 CC BY-NC-ND 4.0( https://creativecommons.org/licenses/by-nc-nd/4.0/deed.zh )协议 的前提下,禁止超过文章30%字数的摘录(对于不超过文章30%字数的摘录,要求在醒目位置注明原文作者与原文链接),同时,在未经作者本人手写签名许可的情况下,禁止任何形式的全文转载,禁止发布任何基于本文的再创作。

题解 AT1121 【通勤電車と気分】 上一篇
题解 AT697 【フィボナッチ】 下一篇
本博客采用 xCss 的 Valine 评论系统,搭配了 Valine-Admin,垃圾评论将会被过滤。所以在评论的时候,请注意您的语言。如果您的评论被过滤但并非垃圾评论,请发邮件到 luosiweimail@gmail.com 进行申诉。