牛客练习赛60 —— 操作集锦

题意简化一下：
给出一个字符串S，求S中有多少个本质不同的长度为k的序列.
题解思路：
其实刚开始看这题的话，思路是懵的。
But：没有思路的时候就看一下数据范围k<=1000,n<=1000
这可能是暗示我们要 n*k的方法去写。

之后我便直接推了一个dp方程：
一、首先：本能反应：

$图片说明$

二、由此可以想到如何去维护这个本质不同的序列个数，考虑到如何做到本质不同？由于题目中给出的字符只有'a'~'z'。所以可以考虑到当长度为k以i结尾时，第k位只有26种可能。

三、考虑维护一个数组表示长度为k时，分别以26个字母结束时的子序列的个数，由于结尾字母不同，可以确保序列本质不同。

四、所以说我们可以推出 :
$图片说明$

五、之后我们就只需要维护f[i]这个数组，考虑到如果同时出现两次c，比如：accd
比如长度为2时，k-1可以为c，可以为a，那么c出现了两次应该使用哪一次呢？——肯定时最后一次了，因为考虑到子序列的问题，前面可以构成的子序列，后面也一定可以构造出来。
六、最后需要特判一下长度m=0(被坑了两发)

/*** keep hungry and calm CoolGuang!***/
//#pragma GCC optimize(2)
#include <bits/stdc++.h>
#include<stdio.h>
#include<algorithm>
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pp;
const ll INF=1e17;
const int maxn=2e5+18;
const int mod=1e9+7;
const double eps=1e-7;
inline bool read(ll &num)
{char in;bool IsN=false;
in=getchar();if(in==EOF) return false;while(in!='-'&&(in<'0'||in>'9')) in=getchar();if(in=='-'){ IsN=true;num=0;}else num=in-'0';while(in=getchar(),in>='0'&&in<='9'){num*=10,num+=in-'0';}if(IsN) num=-num;return true;}
ll n,m,p;
ll dp[1005][1005];///以i结尾长度为k的
ll f[30];
char str[maxn];
int main()
{
    read(n);read(m);
    scanf("%s",str+1);
    if(m==0) printf("1\n");
    else{
        ///dp[i][k]
        for(int i=1;i<=n;i++) dp[i][1]=1;
        for(int k=2;k<=m;k++){///长度为k
            for(int i=1;i<=26;i++) f[i]=0;
            for(int i=1;i<=k-1;i++) f[str[i]-'a'+1]=dp[i][k-1];
            for(int i=k;i<=n;i++){///以str[i]结尾
                for(int j=1;j<=26;j++){
                    dp[i][k]=(dp[i][k]+f[j])%mod;
                }
                f[str[i]-'a'+1]=dp[i][k-1];
            }
        }
        for(int i=1;i<=26;i++) f[i]=0;
        ll ans=0;
        for(int i=n;i>=1;i--)if(!f[str[i]-'a'+1]){
           // printf("%lld\n",dp[i][m]);
            ans=(ans+dp[i][m])%mod;
            f[str[i]-'a'+1]=1;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

此类问题，基本看数据范围首先就应该考虑到二维dp，其次考虑怎么维护限制条件！
代码有疑问的可以在评论中讨论
也欢迎大家指出错误与不足
update:这与序列自动机的写法类似，f的数组也就保证了他是从前面第一个推过来的。
而序列自动机的写法也是保证了每个都是由他前面第一个推过来的！总体而言这个代码可以用序列自动机优化！

牛客练习赛60 —— 操作集锦

全站热榜