linkkk
题意：
给出长度为n的子序列，严格删除m个数后，有多少种子序列。
思路：
很容易想到，用d p [ i ] [ j ]表示从前i个数里删除j个的方案数，枚举第i个是否删除，可以得到d p [ i ] [ j ] = m a x ( d p [ i − 1 ] [ j ] , d p [ i − 1 ] [ j − 1 ] )
但是这样会有重复，比如[ 1 , 2 , 1 , 2 ]，对于[ 1 , 2 ]有3种组合，实际上只算做1种。
记录每个数字上一次出现的位置为p r e，那么重复的方案就是删除[ p r e , i − 1 ]这段后，原p r e的地方便成为i，要减去这部分。
代码：
// Problem: Removal // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/20322/E // Memory Limit: 1048576 MB // Time Limit: 4000 ms // // Powered by CP Editor (https://cpeditor.org) #include<bits/stdc++.h> using namespace std; typedef long long ll;typedef unsigned long long ull; typedef pair<ll,ll>PLL;typedef pair<int,int>PII;typedef pair<double,double>PDD; #define I_int ll inline ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;} #define read read() #define rep(i, a, b) for(int i=(a);i<=(b);++i) #define dep(i, a, b) for(int i=(a);i>=(b);--i) ll ksm(ll a,ll b,ll p){ll res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;} const int maxn=2e5+7,maxm=1e6+7,mod=1e9+7; int n,m,k,a[maxn]; int dp[maxn][12],pre[maxn],pos[maxn]; int main(){ while(cin>>n>>m>>k){ for(int i=1;i<=n;i++) a[i]=read; memset(pos,0,sizeof pos); for(int i=1;i<=n;i++){ pre[i]=pos[a[i]]; pos[a[i]]=i; } //for(int i=1;i<=n;i++) cout<<i<<" "<<pre[i]<<"\n"; memset(dp,0,sizeof dp); dp[0][0]=1; for(int i=1;i<=n;i++){ for(int j=0;j<=min(m,i);j++){ if(j>=1) dp[i][j]=(dp[i][j]+dp[i-1][j-1])%mod; dp[i][j]=(dp[i][j]+dp[i-1][j])%mod; if(pre[i]-1>=0&&j-(i-pre[i])>=0) dp[i][j]=(dp[i][j]-dp[pre[i]-1][j-(i-pre[i])]+mod)%mod; //cout<<i<<" "<<j<<" "<<dp[i][j]<<"\n"; } } cout<<dp[n][m]<<"\n"; } return 0; }
