admin管理员组

文章数量:1575508

用f[i]表示以i为结尾的子串的数目，同时记录字母i最后一次出现时的下标last[i]

那么我们为了达到子串数目最大，考虑下一个字母如何填写。

首先，如果附属字母i，那么此时收到影响的只有f[i],f数组中的其他数值并不受影响

其次，当前加入新的字母的增量，就是所有f的和

最重要的是，利用子串数目的递增性质，也就是f数组中，随着i的增加，f的数值同时也是增加的，这就意味着最早出现的字母必然有着最小的f值

那么很容易想到贪心算法，每次找最小的f值更新，将其更新为最大，也就是每次都填入最早出现的字母，至此算法完毕

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define maxn 1000009
#define rep(i, j, k) for(int i = j; i <= k; i++)
#define mod 1000000007
#define ll long long

using namespace std;

int n, m, k, last[maxn];
ll f[maxn];
char s[maxn];

int main ()
{
	scanf ("%d%d", &n, &k);
	scanf ("%s", s);
	m = strlen (s);
	memset (f, 0, sizeof (f));
	rep (i, 0, m - 1)
	{
		ll now = 0;
		rep (j, 1, k)
			now = (now + f[j]) % mod;
		f[s[i] - 'a' + 1] = (now + 1) % mod;
		last[s[i] - 'a' + 1] = i + 1;
	}
	rep (i, 1, n)
	{
		ll now = 0;
		rep (j, 1, k)
			now = (now + f[j]) % mod;
		ll Min = last[1];
		int p = 1;
		rep (j, 2, k)
			if (last[j] < Min)
				Min = last[j], p = j;
		f[p] = (now + 1) % mod;
		last[p] = maxn + i;
	}
	ll now = 0;
	rep (i, 1, k)
		now = (now +f[i]) % mod;
	cout << (now + 1) % mod << endl;
	return 0;
}

本文标签： 贪心CF645EIntellectualInquiry

版权声明：本文标题：CF645E-Intellectual Inquiry 贪心 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://m.elefans.com/xitong/1727778467a1129086.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。