Codeforces 645E Intellectual Inquiry【dp,构造】

题目链接:

http://codeforces.com/problemset/problem/645/E

题意:

给定字符串,要求用字母表前$k$个字母组成长度为$n$的字符串,并添加在已知字符串后面,使得不同子序列个数最多,求个数。

分析:

设$dp[i]:=前i个元素组成的子序列个数$,则有$dp[i] = dp[i - 1] * 2 - 重复序列个数$.
如何求得重复序列呢?首先对于每个$j \lt i$,我们都保证$dp[j]$中不包含重复序列,那么对于第$i$个元素,只需考虑$s[i]$对于序列的影响即可。而这重复部分即为$s[i]$上一个位置$last[s[i] - ‘a’ ]$之前的所有元素与$s[i]$形成的序列,即重复序列个数=$dp[last[s[i]-‘a’]-1]$。
为使最后的$dp[n + m]$最大,我们要尽量减小$dp[last[s[i]-‘a’]-1]$,而显然$dp$值是单调上升的,构造时每次选取last值最小的即可~~每次得到的$dp$都是最大的,这样累加起来最后得到的而$dp[n+m]$也一定是最大的。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = 2e6 + 5, mod = 1e9 + 7;
char s[maxn];
int dp[maxn];
int last[26 + 5];
int main (void)
{
int n, k;scanf("%d%d", &n, &k);
scanf("%s", s + 1);
int m = strlen(s + 1);
memset(last, -1, sizeof(last));
dp[0] = 1;
int tmp, res;
for(int i = 1; i <= n + m; i++){
if(i <= m) tmp = s[i] - 'a';
else{
res = n + m + 1, tmp = 0;
for(int j = 0; j < k; j++){
if(res > last[j]){
res = last[j];
tmp = j;
if(res == -1) break;
}
}
}
if(last[tmp] > 0) (dp[i] = dp[i - 1] * 2 % mod - dp[last[tmp] - 1] + mod) %= mod;
else dp[i] = dp[i - 1] * 2 % mod;
last[tmp] = i;
}
printf("%d\n", dp[m + n]);
return 0;
}
文章目录
  1. 1. 题目链接:
  2. 2. 题意:
  3. 3. 分析:
  4. 4. 代码: