admin管理员组文章数量:1574959
用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://www.elefans.com/xitong/1727778467a1129086.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论