2016-09-07

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]$也一定是最大的。

代码：

#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;
}