题意
给你一个数组让你在中间删去m个数
问有多少种不同的结果,答案对(1e9+7)取模
思路
简单dp
开一个三维dp,第一维表示当前是第几个数,第二维表示构成的序列最后一个数字是什么,第三维表示还可以删去几次
代码
#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll mod=1e9+7; const int N=1e5+5; int n,m,k; ll dp[N][15][15],a[N]; int main() { while(scanf("%d%d%d",&n,&m,&k)!=EOF) { for(int i=1;i<=n;i++) scanf("%lld",a+i); //清空 for(int i=0;i<=n;i++) for(int j=0;j<=11;j++) for(int kk=0;kk<=11;kk++) dp[i][j][kk]=0; for(int i=1;i<=n;i++) { //当前这个数不删 for(int j=1;j<=k;j++) for(int kk=0;kk<=m;kk++) dp[i][a[i]][kk]=(dp[i][a[i]][kk]+dp[i-1][j][kk])%mod; //前面的数全部删掉 if(i-1<=m) dp[i][a[i]][m-(i-1)]++; //当前的数删掉 for(int j=1;j<=k;j++) { if(j==a[i])//避免重复计算 continue; for(int kk=1;kk<=m;kk++) dp[i][j][kk-1]=(dp[i][j][kk-1]+dp[i-1][j][kk])%mod; } } ll sum=0; for(int i=1;i<=k;i++) sum=(sum+dp[n][i][0])%mod; printf("%lld\n",sum); } return 0; }