【每日一题】Removal

Removal

https://ac.nowcoder.com/acm/problem/17137

solution

表示前个元素,删掉了,所能得到的不同序列的数量。

如果先不考虑不同序列的话,那么就有。也就是种方案。然后考虑减去不合法的方案。

对于一个位置,如果上一个和相等的位置为,那么以结尾的每个序列,都可以通过删掉这个区间变成以结尾的序列。这显然是重复的,所以只要让就行了。

code

/*
* @Author: wxyww
* @Date:   2020-04-24 18:48:43
* @Last Modified time: 2020-04-24 18:59:03
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
using namespace std;
typedef long long ll;
const int N = 100010,mod = 1e9 + 7;
ll read() {
    ll x = 0,f = 1;char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1; c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = x * 10 + c - '0'; c = getchar();
    }
    return x * f;
}
int f[N][12],lst[13];
int main() {
    int n,m,k;
    while(~scanf("%d%d%d",&n,&m,&k)) {
        for(int i = 0;i <= k;++i) lst[i] = 0;

        f[0][0] = 1;

        for(int i = 1;i <= n;++i) {
            int x = read();
            f[i][0] = 1;
            for(int j = 1;j <= min(m,i);++j) {
                f[i][j] = (f[i - 1][j - 1] + f[i - 1][j]) % mod;

                if(lst[x] && (i - lst[x] <= j)) {
                    f[i][j] -= f[lst[x] - 1][j - (i - lst[x])];
                    f[i][j] %= mod;
                }
            }
            lst[x] = i;
        }
        cout<<(f[n][m] + mod) % mod<<endl;
    }
    return 0;
}
全部评论

相关推荐

感性的干饭人在线蹲牛友:🐮 应该是在嘉定这边叭,禾赛大楼挺好看的
点赞 评论 收藏
分享
评论
1
收藏
分享
牛客网
牛客企业服务