题目大意:
给定一个 个数字的序列,序列中的数字在 中,从序列中删去 个数字,问能得到多少种不同的序列。
知识点: 动态规划
解题思路(from ftiasch):
把问题转换成考虑有多少种方案可以构成一个有 个数字的序列,而且这个序列是由给定的原数字序列删掉 个数字而得到的。
设 ,其中 代表当前遍历到的数字序列的下标, 代表当前已经删掉的数字个数, 代表当前已经构造完毕的数字序列的最后一个数字。
对于这个 ,我们只需要遍历原数字序列的每一个数字(其实就是把 数组由 推到 ),然后对于满足 的 ,考虑不把当前遍历到的数字放进去(其实就相当于删除掉当前遍历到的数字),进行如下转移:
当然,我们总是可以选择把遍历到的数字放进构造的数字序列中,此时进行的是这样的转移:
不难发现,对于每一次从 到 的转移, 前面的信息其实都是没用的,所以我们可以只用一个 来保存 中的信息,用 来记录更新出来的 。每次更新完后再将 中的信息放入 中即可。
AC代码:
#include <bits/stdc++.h> using namespace std; const int MOD=1e9+7; const int MAXN=1e5+5; int dp[15][15],new_dp[15][15]; int s[MAXN]; int main(){ int n,m,k; while(~scanf("%d%d%d",&n,&m,&k)){ memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) scanf("%d",&s[i]); dp[0][0]=1; for(int index=1;index<=n;index++){ memset(new_dp,0,sizeof(new_dp)); for(int delet=0;delet<=m;delet++){ for(int now=0;now<=k;now++){ if(delet<m&&now!=s[index]) new_dp[delet+1][now]=(new_dp[delet+1][now]+dp[delet][now])%MOD; new_dp[delet][s[index]]=(new_dp[delet][s[index]]+dp[delet][now])%MOD; } } for(int delet=0;delet<=m;delet++){ for(int now=0;now<=k;now++) dp[delet][now]=new_dp[delet][now]; } } int ans=0; for(int i=0;i<=k;i++) ans+=dp[m][i],ans%=MOD; printf("%d\n",ans); } return 0; }
全部评论
(0) 回帖