首页 > 代码库 > CodeForces 645E Intellectual Inquiry
CodeForces 645E Intellectual Inquiry
$dp$，贪心。
不得不说这题出的很$6$，解法更$6$。
首先要会统计一个字符串有多少个本质不同的子序列，有两种$dp$策略：
①$dp[i]$表示$[1,i]$内的字符有多少种本质不同的子序列，$dp[i]=2*dp[i-1]-dp[pre[s[i]]-1]$，如果$s[i]$是第一次出现，那么$dp[i]$还需要额外$+1$。$pre[x]$表示字符$x$上一次出现的位置。
$dp[i]$可以理解为$[1,i-1]$的种类数保留下来，再加上$[1,i-1]$每一种后面加上一个字符$x$，但是这样加多了，因为$[1,pre[x]-1]$区间内的种类加上字符$x$多统计了一次，所以要减掉。最终答案为$dp[n]$。
②$dp[i][j]$表示$[1,i]$内的字符，以字符$j$为结尾的本质不同的子序列的个数。
如果$s[i]≠j$，那么$dp[i][j]=dp[i-1][j]$；否则$dp[i][j] = \sum\limits_{p = 1}^k {dp[i - 1][p]}+1$ 。最终答案为：$\sum\limits_{p = 1}^k {dp[n][p]}$。
就这题而言的话，利用方法②很容易理解。
首先将$t$串的不同子序列的个数统计好，然后就是要再在后面加上$n$个自己构造的字符。观察递推式，会发现每一次是将$\sum\limits_{p = 1}^k {dp[i - 1][p]}+1$赋值给一个$dp[i][x]$，其余的$dp[i][y]$保留之前的。因为答案要求最大值，所以肯定是选择将$dp[i-1][x]$最小的重新赋值，其余保留。
注意到不能直接寻找最小值，因为进行了取模，观察后会发现只要知道哪一个字符最后出现的位置最早就可以了，因为那个$dp$是递增的，越早出现的$dp$值肯定是越小的。
#pragma comment(linker, "/STACK:1024000000,1024000000")#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#include<vector>#include<map>#include<set>#include<queue>#include<stack>#include<bitset>#include<iostream>using namespace std;typedef long long LL;const double pi=acos(-1.0),eps=1e-6;void File(){ freopen("D:\\in.txt","r",stdin); freopen("D:\\out.txt","w",stdout);}template <class T>inline void read(T &x){ char c=getchar(); x=0; while(!isdigit(c)) c=getchar(); while(isdigit(c)) {x=x*10+c-‘0‘; c=getchar();}}const int maxn=1000010;int n,k,pre[maxn];LL f[30],mod=1e9+7;char s[maxn];int main(){ scanf("%d%d",&n,&k); scanf("%s",s); int m=strlen(s); for(int i=1;i<=m;i++) { LL sum=0; for(int j=1;j<=k;j++) sum=(sum+f[j])%mod; f[s[i-1]-‘a‘+1]=(sum+1)%mod; pre[s[i-1]-‘a‘+1]=i; } for(int i=m+1;i<=m+n;i++) { LL sum=0; for(int j=1;j<=k;j++) sum=(sum+f[j])%mod; int mx=3*maxn,mi; for(int j=1;j<=k;j++) if(pre[j]<mx) mi=j,mx=pre[j]; f[mi]=(sum+1)%mod; pre[mi]=i; } LL ans=0; for(int i=1;i<=k;i++) ans=(ans+f[i])%mod; printf("%lld\n",(ans+1)%mod); return 0;}
CodeForces 645E Intellectual Inquiry