Removal

Problem:

n 个数,去除任意 m 个数,问最终能形成多少种不同的序列,对答案取模 1e9 + 7 输出

Solution:

设 dp[i][j] = k 表示前k个数,去除 m 个有 k 种
dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1] (dp[i - 1][j]:表示不去除第i个数;dp[i - 1][j - 1]:表示去除第i个数)
重复现象:
对于1,2,3,4,3,2,1,5来说,去除两个数的话会出现 (1,2,,,3,2,1,5),(1,2,3,,,2,1,5)这两种情况,而这两种得到的序列都是重复的
因此,我们计算的时候需要避免这种情况。
出现重复的原因就是删除连续数中存在两个相同的数，而重复的数量就是当前数a的位置为indexNow，上一次a出现的位置为indexLast，
固定（indexLast，indexNow）区间的数字和相同的两个数其中一个（indexLast或者indexNow）一定会被删除，而剩余还需要删除的数，
即从indexLast-1之前的数里面找j - （indxNow - indexLast））个。
因此重复的时候状态转移方程是
dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1] - dp[indexLast - 1][j - (i - indexLast)]

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define _for(i,s,t) for(int i=s;i<t;i++)
#define _rof(i,s,t) for(int i=s;i>t;i--)
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define per(i,s,t) for(int i=s;i>=t;i--)
#define Ri(x) scanf("%d",&x)
#define Rii(x,y) scanf("%d%d",&x,&y)
#define INF 0x3f3f3f3f
using namespace std;
template<class T>inline void read(T &res)
{
    char c;T flag=1;
    while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
    while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
}
typedef long long ll;
const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;
ll dp[maxn][11];
int s[maxn];
int main(){
    IOS;
    int n,m,k;
    while(cin>>n>>m>>k){
        rep(i,1,n){
            cin>>s[i];
        }
        dp[0][0] = 1;
        rep(i,1,n){// 第几个数
            dp[i][0] = 1; 
            rep(j,1,m){// 去除几个 
                dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
                dp[i][j] %= mod;
                if(i - j > 0)
                for(int k = i - 1;k >= (i - j);k --){
                    if(s[i] == s[k]){
                        dp[i][j] -= dp[k - 1][j - (i - k)];
                        dp[i][j] = (dp[i][j] + mod) % mod;
                        break;// 删除一个就好了，前面再有与i相同的数已经被当前这个k计算过了，所以不会被加入到dp[i][j] 
                    }
                }
            }
        }
        cout<<(dp[n][m] + mod) % mod<<endl;
    }
    return 0;
}
/**
Problem:
    n 个数,去除任意 m 个数,问最终能形成多少种不同的序列,对答案取模 1e9 + 7 输出
Solution:
    设 dp[i][j] = k 表示前k个数,去除 m 个有 k 种
    dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1] (dp[i - 1][j]:表示不去除第i个数;dp[i - 1][j - 1]:表示去除第i个数)
    重复现象:
        对于1,2,3,4,3,2,1,5来说,去除两个数的话会出现 (1,2,*,*,3,2,1,5),(1,2,3,*,*,2,1,5)这两种情况,而这两种得到的序列都是重复的
        因此,我们计算的时候需要避免这种情况。
        出现重复的原因就是删除连续数中存在两个相同的数，而重复的数量就是当前数a的位置为indexNow，上一次a出现的位置为indexLast，
        固定（indexLast，indexNow）区间的数字和相同的两个数其中一个（indexLast或者indexNow）一定会被删除，而剩余还需要删除的数，
        即从indexLast-1之前的数里面找j - （indxNow - indexLast））个。
        因此重复的时候状态转移方程是
        dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1] - dp[indexLast - 1][j - (i - indexLast)] 
*/