Luogu-P4832

题面

题目大意是珈百璃不想写作业就把作业交给了你,给你一些形如s+c的式子,其中s代表 $sin\frac{\pi}{7}$ ,c代表 $cos\frac{\pi}{7}$ ,然后你可以从中间选一些式子,要求最后选出的式子之和为整数最大

给一组样例的输入

3

s+c

s+c+s

c

对应的输出为

3

看到题目首先想到一定有 $sin\frac{\pi}{7} + cos\frac{\pi}{7} = 1$,那么很显然的我们要想使得结果为整数,选出的式子中的s与c的数量要相同

则问题就成了怎样选式子使得s与c的数量相同且使得答案尽可能的大

考虑状态转移函数 $F(i, s, c)$ 其中 $i$ 已经选过了第 $i$ 个式子, $s, c$分别代表选完后的s与c的数量,而函数的值本身代表选完 $i$ 个式子后总和的最大整数值
则一定有

(一个必要的条件是当前的s, c一定要是可达的,如果我不论怎么选都选不出这样的s与c那么这个结论肯定不成立)

当然这个结论说了和没说一样
还需要有状态转移方程

其中 $s_i, c_i$ 代表第 $i$ 个式子中的s与c的个数,$\Delta$ 则是选中了这个式子后当前式子总和的值的增量
这里 $\Delta$ 的值要分类讨论

当 $s - s_i$ 与 $c - c_i$ 相等时,很容易想到 $\Delta = min\{s_i, c_i\}$

当 $s - s_i$ 不等于 $c - c_i$ 时,$\Delta = min\{s, c\} - min\{s - s_i, c - c_i\}$ (想一想为什么)

那么答案就是所有 $max\{F(i, t, t)\}, (0 < t \leq N)$

有了上边这些结论,我们貌似就可以AC这道题了,但是但是先等等,这个算法的时间复杂度为 $O(NSC)$, ($S, C$ 分别代表所有式子中的s,c数量之和)

默默看了眼数据范围大喊卧槽(自己点击去看看吧),这明显会MLE。哭了

冥思苦想一下有了新的想法,我们的状态转移函数中的s,c明显就是冗余的数据,其实只要记录下s与c的差值d就可以 那么有

不过这样写会麻烦不少,因为需要处理d为负数的情况,并且对于d可谓负数的情况不可以直接简单的反向遍历数组。

AC代码

1
#include <iostream>
2
#include <algorithm>
3
4
using namespace std;
5
6
const int maxm = 1e6 + 15;
7
const int Inf = 0x3f3f3f3f;
8
const int D = 50000;
9
10
inline auto real(int x) -> int {
11
    return x + maxm;
12
}
13
14
auto split(string & s) -> pair<int, int> {
15
    int si = 0, ci = 0;
16
    for (auto &&c : s) {
17
        if(c == 'c') ++ci;
18
        if(c == 's') ++si;
19
    }
20
    return {si, ci};
21
}
22
23
int F[2][2 * maxm];
24
25
auto main() -> int {
26
    ios::sync_with_stdio(false);
27
    cin.tie(nullptr);
28
    cout.tie(nullptr);
29
    int n;
30
    cin >> n;
31
    int l = 0, r = 0;
32
    fill(F[0], F[0] + 2 * maxm, -Inf);
33
    fill(F[1], F[1] + 2 * maxm, -Inf);
34
    F[0][real(0)] = 0;
35
    for (int i = 1; i <= n; ++i) {
36
        string s;
37
        cin >> s;
38
        auto [si, ci] = split(s);
39
        int d = si - ci;
40
        l = min(l, l + d);
41
        r = max(r, r + d);
42
        for (int j = l; j <= r; ++j) {
43
            F[i % 2][real(j)] = max(F[i % 2][real(j)], F[i % 2 ^ 1][real(j)]);
44
            F[i % 2][real(j)] = max(F[i % 2][real(j)], F[i % 2 ^ 1][real(j - d)] + ci);
45
        }
46
    }
47
    cout << F[n % 2][real(0)] << endl;
48
    return 0;
49
}