Codeforces 645E. Intellectual Inquiry（DP，贪心）

Codeforces 645E. Intellectual Inquiry

题意：给定一串字符，由前k个小写拉丁字母组成，要求在该字符串后面补上n个字符（也从前k个小写拉丁字母里面选），使得最后得到的字符串含有本质不同的子序列的数量最大。

思路：要解决这个问题，首先要解决如何求字符串本质不同的子序列的个数的问题。定义dp[i][j]表示前i个字符内，以字符j结尾的本质不同的子序列的个数。那么可推得转移式：s[i]==j时，dp[i][j] = \(\sum_{t=1}^{k}dp[i-1][t]\) +1 (s[i]可自成一个子序列，故+1);s[i]!=j时，则dp[i][j]=dp[i-1][j].则最后答案为 \(\sum_{t=1}^{k}dp[len][t]\) 。接下来解决补n个字符的问题，观察dp转移式可以发现，每次会把 \(\sum_{t=1}^{k}dp[i-1][t]\) +1 赋给dp[i][s[i]]，其余的则直接赋dp[i-1]对应的值，保持不变。因此要想使最后的答案最大，每次应该给最小的dp[i][j]赋值，因此后面的n个字符，每次都要填当前dp值最小的那个字符，而观察可知那个字符一定是最后出现位置最靠前的那个，因为dp值是递增的，越迟出现值一定越大。

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<map>

#include<queue>

#include<string>

#include<vector>

#include<cmath>

#include<climits>

#include<functional>

#include<set>

#define dd(x) cout<<#x<<" = "<<x<<" "

#define de(x) cout<<#x<<" = "<<x<<endl

#define fi first

#define se second

#define mp make_pair

#define pb push_back

using namespace std;

typedef long long ll;

typedef pair<int,int> P;

typedef vector<int> V;

typedef map<int,int> M;

typedef queue<int> Q;

typedef priority_queue<int> BQ;

typedef priority_queue<int,vector<int>,greater<int> > SQ;

const int maxn=1e6+10,INF=0x3f3f3f3f,mod=1e9+7;

int dp[30],last[30];

char s[maxn<<1];

inline int add(int a,int b)

{

  a+=b;

  if (a>=mod)

  	a-=mod;

  return a;

}

int sum(int k)

{

  int res=0;

  for (int i=0;i<k;++i)

  	res=add(res,dp[i]);

  return res;

}

int main()

{

	int n,k;

	scanf("%d%d%s",&n,&k,s+1);

	int m=strlen(s+1);

	for (int i=1;i<=m;++i)

	{

	  int c=s[i]-'a';

	  dp[c]=sum(k)+1;

	  last[c]=i;

	}

	for (int i=m+1;i<=m+n;++i)

	{

	  int c=min_element(last,last+k)-last;

	  dp[c]=sum(k)+1;

	  last[c]=i;

	}

	printf("%d",add(sum(k),1));

	return 0;

}

巴特西

Codeforces 645E. Intellectual Inquiry（DP，贪心）

最新文章

热门文章