admin管理员组文章数量:1574959
题意:给出一个字符串t,现在可以在这个字符串后面加n个k以下的字母,询问一种方案,使得加了n个字母后的字符串中不相同的子串(子串不一定连续)最多。
思路:首先先看给定的字符串t,要解决的第一个问题是要如何求字符串t中不相同的子串数量。
这一步可以dp来做,用dp[i]表示位置i之前的子串数量,假设当前已经考虑到了第i个位置,也就是说之前的dp[0]~dp[i-1]已经求了出来,
再用pos[j]表示字符j上次出现的位置
对于当前位置i来说,因为比上一次多了一个字符,所以会增加dp[I-1]个以当前字符结尾的新子串,但是这些子串中有重复的,也就是以当前字符上次位置作为结束位置的子串数量。
所以可以得到转移方程dp[I] = dp[I-1] * 2 - dp[ pos[t[I] - 1] ];
剩下的问题就是向这个字符串后面加字符串了,怎么加才能使最后的字符串子串数量最多呢,方法是每加一个位置都取当前的最优解,也就是局部的最优解就是整体的最优解
可以贪心的来想,考虑字符串后的第一个位置,肯定是加之前所有pos[j]中最小的,然后就确定了这一步的位置,然后每一步都这样取最优解
但这样是否能保证最后的解一定是最优解呢?答案是肯定的,因为根据上面的转移方程其实最后的子串数量等于
(dp[len]<<n) - (pos1<<(n-1)) - (pos2<<(n-2)) - ......posn (posk为第k个位置选取的位置)
可以看到每一项的权值都大于后面的所有项的和,所以局部最优可以保证全局最优。
#include<bits/stdc++.h>
#define eps 1e-6
#define LL long long
#define pii pair<int, int>
#define pb push_back
#define mp make_pair
//#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
const int MAXN = 1000100;
const int MOD = 1e9+7;
int n, k;
LL dp[MAXN];
int pos[30];
char t[MAXN];
int main()
{
freopen("input.txt", "r", stdin);
scanf("%d%d%s", &n, &k, t+1);
int len = strlen(t+1);
dp[0] = 1;
for (int i = 1; i <= len; i++) {
dp[i] = (dp[i-1]<<1);
if (pos[t[i]-'a'] > 0)
dp[i] -= dp[pos[t[i]-'a']-1];
dp[i] %= MOD;
pos[t[i]-'a'] = i;
}
for (int i = len+1; i <= len+n; i++) {
dp[i] = (dp[i-1]<<1);
int id, p = i;
for (int j = 0; j < k; j++) {
if (pos[j] < p) {
p = pos[j];
id = j;
}
}
if (p > 0)
dp[i] -= dp[p-1];
dp[i] %= MOD;
pos[id] = i;
}
printf("%d", (dp[len+n]+MOD)%MOD);
return 0;
}
本文标签: 贪心codeforcesIntellectualDPInquiry
版权声明:本文标题:CodeForces 645E Intellectual Inquiry(构造+贪心+dp) 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dianzi/1727778486a1129088.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论