竞赛讨论区 > 牛客网暑期ACM多校训练营(第一场)E、Removal 题解
头像
xseventh
编辑于 2018-07-19 23:25
+ 关注

牛客网暑期ACM多校训练营(第一场)E、Removal 题解

E题解法:
这题相当于求有多少种不同的长度为n-m的子序列。
我们可以用dp来求解。
我们定义dp[i][j]代表长度为i,最末尾的数字为j的子序列方案数,sum[i]代表长度为i的子序列个数
我们初始令sum[0]=1
很容易写出O(n^2)复杂度的解法
for(int i=1;i<=n;i++){//每次增加一个字符
    for(int j=i;j>=1;j--){//从长到短枚举子序列长度
        sum[j]+=(sum[j-1]-dp[j][s[i]])%mod;//因为dp[j][s[i]]要等于sum[j-1],这样长度为j的子序列方案数发生了变化,所以我们要修改sum[j]的值
        sum[j]%=mod;
        dp[j][s[i]]=sum[j-1];
    }
}
最终的sum[n-m]就是我们要求的答案
然后怎么优化呢,我们发现,每次sum[j]和dp[j]只会由sum[j-1]和dp[j-1]推出来,而我们需要的只有sum数组的倒数第m个数字,m又非常小。
这时候一个很简单的优化就出来了
for(int i=1;i<=n;i++){//每次增加一个字符
    for(int j=i;j>=1&&j>=i-m-1;j--){//从长到短枚举子序列长度,这里只需要维护最后m个就行了,保险起见我***护了一个数。
        sum[j]+=(sum[j-1]-dp[j][s[i]])%mod;//因为dp[j][s[i]]要等于sum[j-1],这样长度为j的子序列方案数发生了变化,所以我们要修改sum[j]的值
        sum[j]%=mod;
        dp[j][s[i]]=sum[j-1];
    }
}
只要在第二层for里加一个限制条件就好了,我们只dp最后m个数字,而之前的是我们不需要的,这样一个O(n*m)复杂度的算法就出来了。注意取模就可以AC啦



完整代码
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
int s[111111];
int dp[111111][11],sum[111111];///长度为i 结尾为j
///
int main(){
    int n,m,k;
    while(~scanf("%d%d%d",&n,&m,&k)){
        for(int i=1;i<=n;i++){
            scanf("%d",s+i);
        }
        memset(sum,0,sizeof(sum));
        memset(dp,0,sizeof(dp));
        sum[0]=1;
        for(int i=1;i<=n;i++){
            for(int j=i;j>=1&&j>=i-m-1;j--){
                sum[j]+=(sum[j-1]-dp[j][s[i]])%mod;
                sum[j]%=mod;
                dp[j][s[i]]=sum[j-1];
            }
        }
        int ans=sum[n-m]%mod;
        ans+=mod;
        ans%=mod;
        printf("%d\n",ans);
    }
    return 0;
}

全部评论

(0) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐