牛客网暑期ACM多校训练营（第一场）：E-Removal（DP）

题意：给出序列 s₁, s₂, ..., s_n ，1<=s[i]<=10。问删除m个数后，有多少种不同的序列。

题解：定义dp[i][j]代表长度为i，最末尾的数字为j的子序列方案数，sum[i]代表长度为i的子序列个数。

　　　sum[0] = 1。

　　　从 1 ~ n 遍历序列，当遍历到 s[i] 时 sum[1] ~ sum[i] 就会增加一些以 s[i] 结尾的情况。状态转移：sum[j] += (sum[j-1] - dp[j][s[i]]) % mod。多增加的情况就是 sum[j-1] 后面在增加一个 s[i] ，但是如果以 s[i] 结尾的序列以前就出现过，那么新增加的情况中就会有 dp[j][s[i]] 个重复的情况，减去即可。dp[j][s[i]] = sum[j-1]，因为结尾是 s[i] 已经定了，能变得就只剩下前面 j-1 个了。

#include <bits/stdc++.h>

using namespace std;

const double EPS = 1e-;

const int INF = 0x3f3f3f3f;

const int mod = 1e9 + ;

const int maxn = 1e5 + ;

int n, m, k;

int s[maxn];

long long dp[maxn][];

long long sum[maxn];

int main()

{

    while(scanf("%d%d%d", &n, &m, &k) != EOF){

        for(int i = ; i <= n; i++) scanf("%d", &s[i]);

        memset(dp, , sizeof(dp));

        memset(sum, , sizeof(sum));

        sum[] = ;

        for(int i = ; i <= n; i++){

            for(int j = i; j >=  && j >= i - m; j--){

                sum[j] += (sum[j-] - dp[j][s[i]]) % mod;

                dp[j][s[i]] = sum[j-];

            }

        }

        printf("%lld\n", (sum[n-m] % mod + mod) % mod);

    }

    return ;

}

巴特西

牛客网暑期ACM多校训练营（第一场）：E-Removal（DP）

最新文章

热门文章