珈百璃堕落的开始

GitHub 跳转原题关系图返回列表

把每个式子化成 `(#s-#c, #s+#c)`，再做差值背包，求总差值为 0 时总长度最大，答案就是长度的一半。

OJ: luogu

题目 ID: P4832

难度:提高+/省选-

标签:动态规划背包数学状态设计

日期: 2026-06-21 07:59

题意

每个式子由若干个 s 和 c 相加组成，其中：

s = sin^2(pi/7)
c = cos^2(pi/7)

可以从给定式子中选一些相加，要求结果是整数，并且这个整数尽量大。

思路

先看小数据暴力：

cpp

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#include <bits/stdc++.h>
using namespace std;

const int NEG_INF = -0x3f3f3f3f;

int n;
vector<int> diff_val, len_val;
int best_answer;

void dfs(int idx, int diff_sum, int len_sum) {
    if (idx == n) {
        if (diff_sum == 0) {
            best_answer = max(best_answer, len_sum / 2);
        }
        return;
    }

    // 不选当前式子。
    dfs(idx + 1, diff_sum, len_sum);
    // 选当前式子。
    dfs(idx + 1, diff_sum + diff_val[idx], len_sum + len_val[idx]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // brute.cpp：小数据暴力枚举。
    // 直接枚举每个式子选或不选，统计总差值是否为 0。
    cin >> n;
    diff_val.resize(n);
    len_val.resize(n);

    for (int i = 0; i < n; i++) {
        string str;
        cin >> str;
        int cnt_s = 0;
        int cnt_c = 0;
        for (unsigned int j = 0; j < str.size(); j++) {
            if (str[j] == 's') {
                cnt_s++;
            } else if (str[j] == 'c') {
                cnt_c++;
            }
        }
        diff_val[i] = cnt_s - cnt_c;
        len_val[i] = cnt_s + cnt_c;
    }

    best_answer = 0;
    dfs(0, 0, 0);
    cout << best_answer << '\n';
    return 0;
}

设：

a = sin^2(pi/7)
b = cos^2(pi/7)

有恒等式：

a + b = 1

于是一个式子只需要关心两件事：

它一共有多少个字符，记作 len
它的 s 比 c 多多少，记作 diff = #s - #c

如果最终选中的所有式子总共有：

S 个 s
C 个 c

那么总和是：

S * a + C * b

只有当 S = C 时，才能全部配成若干个 a+b=1，结果才是整数。

而这时答案正好就是：

(S + C) / 2

所以题目变成：

选出若干个式子，使总差值 diff 为 0，并让总长度最大。

这就是一个差值背包：

状态：总差值为某个值时的最大总长度
转移：每个式子选或不选

DP 转移方程

设第 i 个式子的差值为 diff_i，长度为 len_i。若当前总差值是 d，选择这个式子后：

dp[d+diff_i]=\max(dp[d+diff_i],\ dp[d]+len_i)

代码里会给差值整体加一个偏移量，避免出现负下标。

最后输出：

dp[0] / 2

代码

cpp

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#include <bits/stdc++.h>
using namespace std;

const int MAXM = 1000005;
const int NEG_INF = -0x3f3f3f3f;

int n;
int diff_val[MAXM], len_val[MAXM];
int total_abs_diff;
int dp[2 * MAXM + 5];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        string str;
        cin >> str;
        int cnt_s = 0;
        int cnt_c = 0;
        for (unsigned int j = 0; j < str.size(); j++) {
            if (str[j] == 's') {
                cnt_s++;
            } else if (str[j] == 'c') {
                cnt_c++;
            }
        }
        diff_val[i] = cnt_s - cnt_c;
        len_val[i] = cnt_s + cnt_c;
        total_abs_diff += abs(diff_val[i]);
    }

    int offset = total_abs_diff;
    for (int i = 0; i <= 2 * total_abs_diff; i++) {
        dp[i] = NEG_INF;
    }
    dp[offset] = 0;

    int cur = 0;
    for (int i = 1; i <= n; i++) {
        if (diff_val[i] >= 0) {
            for (int d = cur; d >= -cur; d--) {
                if (dp[d + offset] == NEG_INF) {
                    continue;
                }
                int nd = d + diff_val[i];
                dp[nd + offset] = max(dp[nd + offset], dp[d + offset] + len_val[i]);
            }
        } else {
            for (int d = -cur; d <= cur; d++) {
                if (dp[d + offset] == NEG_INF) {
                    continue;
                }
                int nd = d + diff_val[i];
                dp[nd + offset] = max(dp[nd + offset], dp[d + offset] + len_val[i]);
            }
        }
        cur += abs(diff_val[i]);
    }

    cout << dp[offset] / 2 << '\n';
    return 0;
}

复杂度

时间复杂度 $O(nm)$ ，空间复杂度 $O(m)$ ，其中 m 是题目中的总字符规模量。

总结

这题最关键的不是三角函数，而是把它转化成：

差值是否能配平
配平后总长度尽量大

一旦想到 sin^2x + cos^2x = 1，就会变成很自然的背包题。

P4832 珈百璃堕落的开始

题目背景

“恭喜你，珈百璃，你以学年首席的优秀成绩毕业。”

珈百璃，一位优秀的天使，今天她以学年首席的成绩毕业，从今往后，她将前往人间进行进一步修炼。

“我会努力给人类带来幸福的！”珈百璃憧憬着人间生活。

开学第一天，珈百璃就凭借着她极其可爱的外表，受到了班级成员的追捧，不仅长得可爱，成绩还很优秀，简直就是女神啊！

因为她的成绩优秀，所以她的作业也是很快就快要完成了，但是就在她快完成数学作业时，她的电脑传来了呼救的声音。

“救命啊！”

顺着这个呼救声，珈百璃望向了电脑。

“原来是游戏啊。”珈百璃看着屏幕里一位倒在地上的残血战士，注册了账号，选择了牧师职业，对这位战士进行了救治。在珈百璃开心的同时，越来越多的呼救声传来，珈百璃一个一个进行救治，但她的 level 才 1，mp 肯定不足，当她想要继续进行救治的时候，系统提示 mp 不足，并给出了氪金的提示：“屠龙宝刀，点击就送。”

“生活费天界学院倒是有给，但是……”珈百璃看着自己的存折，再看看屏幕，她纠结不已。

“救命啊！”“救……救命啊……”“救命啊！”珈百璃看着这些人一个个喊出救命，自己却无能为力，终于，她控制不住自己，点下了“氪金”按钮。

从此，珈百璃的堕落就开始了，她的作业，也停在了这道数学题上……

“薇奈特，帮我写一下作业嘛。”珈百璃央求着薇奈特。

“真是的，你好歹也是天使呢，也该自己做一点作业吧。”

“不要，我还要打游戏呢。”

“这怎么行，你是天使啊。”

“我已经决定做一位成天打游戏不学习的堕天使了。”

“真是服了你啊，那你好好打游戏吧，我帮你写。”

题目描述

这道题是这样的：给定一些 $\sin^2x$ ， $\cos^2x\ \left(x=\dfrac{\pi}{7}\right)$ 组成的式子，请你帮忙求出选择一些式子相加后得到的最大整数答案。

输入格式

第一行一个整数 $n$ ，表示 $n$ 个式子

接下来 $n$ 行每行一个字符串，由 $f(i)=\sin^2x,\cos^2x$ 和加号组成， $x=\dfrac{\pi}{7}$ 。

为了简化输入，我们以 s 代表 $\sin^2x$ ，以 c 代表 $\cos^2x$ ，并省略 f(i)=。

输出格式

一个数表示最大整数答案，计算全部为加法。

输入输出样例 #1

输入 #1

text

1
2
3
43
s+c
s+c+s
c

输出 #1

text

说明/提示

样例解释

三个式子都选，则加起来等于 $3$ 。

数据范围

设 s 和 c 的个数总和为 $m$ 。

$10\%$ 的数据 $n=1$ 。

另外 $20\%$ 的数据每行一个单项式。

另有 $20\%$ 的数据 $n\le20$ 。

$100\%$ 的数据 $n\times m\le5\times10^7,m\le10^6$ 。

提示

$\forall x, \sin^2x+\cos^2x=1$ 。

珈百璃堕落的开始

目录

题意

思路

DP 转移方程

代码

复杂度

总结