头像
Blogggggg
编辑于 2018-07-22 14:35
+ 关注

Removal

题目大意:
给定一个 个数字的序列,序列中的数字在 中,从序列中删去 个数字,问能得到多少种不同的序列。


知识点: 动态规划

解题思路(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) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐