hyz's blog
0%

CF 900E: Maximum Questions

发表于

题意

给一个长度为n（1 ≤ n ≤ 100000）的字符串，这个字符串只包含‘a’，’b’，‘?’三种字符，其中’?’可以变成‘a’或‘b’。现在需要求这个字符串里包含最多个长度为m（m <= n)的字符串时的最小转变次数是多少，需要注意的是两个长度为m的字符串不能重叠。这个长度为m的字符串的构造规则是ababab…即奇数位为a，偶数位为b。

分析

看完题意，容易发现应该用DP来写。但是，怎么判断某一个长度为m的子串是否为合法串以及构成合法串所需的花费呢？这需要我们用前缀和分奇偶统计a，b出现的次数，然后就可以在O(1)的时间判断了。接着，进行DP，dp[i].cost 表示前面i个字符构成最多合法串时的最小花费，dp[i].ma表示前面i个字符构成最多合法串的个数。dp[i] 可以由dp[i-1]或dp[i-m]转移过来，转移的条件是构成的合法串更多或者构成的合法串一样多但是花费更少。最后，dp[n].cost 即为答案。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

#include<bits/stdc++.h>
#define x first
#define y second
#define ok cout << "ok" << endl;
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const double PI = acos(-1.0);
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const int N=1e5+9;
const int shift=1e3+9;
const double Eps=1e-7;

int a[N], b[N], c[N], d[N], n, m;
string s;

struct node {
    int ma, cost;
}dp[N];

int main(void) {
    if(fopen("in", "r")!=NULL) {freopen("in", "r", stdin); freopen("out", "w", stdout);}
    while(cin >> n >> s >> m) {
        s = '0' + s;
        int len = s.length();
        memset(a, 0, sizeof a);
        memset(b, 0, sizeof b);
        memset(c, 0, sizeof c);
        memset(d, -1, sizeof d);
        //按照奇偶下标统计a以及?出现的次数，存储到a[]
        //按照奇偶下标统计b以及?出现的次数，存储到b[]
        //统计?出现的次数，存储到c[]
        for(int i = 1; i < len; i++) {
            c[i] = c[i-1] + (s[i] == '?' ? 1 : 0);
            if(i >= 2) {
                a[i] = a[i-2] + (s[i] == '?' || s[i] == 'a' ? 1 : 0);
                b[i] = b[i-2] + (s[i] == '?' || s[i] == 'b' ? 1 : 0);
            }
            else {
                a[i] = (s[i] == '?' || s[i] == 'a' ? 1 : 0);
                b[i] = (s[i] == '?' || s[i] == 'b' ? 1 : 0);
            }
        }
        //判断以i结尾的字符串是否有可能合法，假如有可能，d[]为花费，假如不可能，d[]为-1
        for(int i = m; i < len; i++) {
            if(m & 1) {
                int ta = a[i] - a[max(0, i - m - 1)];
                int tb = max(0, b[i-1] - b[max(0, i - m)]);
                if(ta >= (m+1)/2 && tb >= m/2)
                    d[i] = c[i] - c[i-m];
            }
            else {
                int ta = a[i-1] - a[max(0, i - m - 1)];
                int tb = b[i] - b[i - m];
                if(ta >= (m+1)/2 && tb >= m/2)
                    d[i] = c[i] - c[i-m];
            }
        }
        memset(dp, 0, sizeof dp);
        //dp[i]可以由dp[i-m]以及dp[i-1]转移过来，更优的标准是凑出更多的合法串或者让一样多的合法串花费更少
        for(int i = m; i < len; i++) {
            if(d[i] == -1)
                dp[i] = dp[i-1];
            else if(dp[i-m].ma + 1 > dp[i-1].ma || (dp[i-m].ma + 1 == dp[i-1].ma && dp[i-m].cost + d[i] < dp[i-1].cost))
                dp[i].ma = dp[i-m].ma + 1, dp[i].cost = dp[i-m].cost + d[i];
            else
                dp[i] = dp[i-1];
        }
        printf("%d\n", dp[len-1].cost);
    }
    return 0;
}