打卡信奥刷题（2856）用C++实现信奥题 P4832 珈百璃堕落的开始

P4832 珈百璃堕落的开始

题目背景

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

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

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

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

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

“救命啊！”

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

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

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

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

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

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

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

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

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

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

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

题目描述

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

输入格式

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

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

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

输出格式

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

输入输出样例 #1

输入 #1

3
s+c
s+c+s
c

输出 #1

3

说明/提示

样例解释

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

数据范围

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

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

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

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

$100\%$ 的数据 $n\times m\le 5\times 10^7,m\le 10^6$。

提示

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

C++实现

#include <cstdio>
#include <cstring>
using namespace std;

const int inf = 100000000;
const int T = 1000300;
int N, sum[2], dp[2][2001005], l, r;
char s[2000005];

inline int max(int x, int y)
{
return x>y? x: y;
}
inline int min(int x, int y)
{
return x<y? x: y;
}
int main()
{
scanf("%d", &N);
for (register int i=0; i<=2001000; ++i) dp[0][i] = dp[1][i] = –inf;
dp[0][T] = 0;
for (register int i=1, ls; i<=N; ++i) {
scanf("%s", s), ls = strlen(s);
sum[0] = 0, sum[1] = 0;
for (register int j=0; j<ls; j+=2) if (s[j]=='c') sum[0]++; else sum[1]++;
int w = sum[0], v = sum[1] – sum[0];
l = min(l, l+v), r = max(r, r+v);
for (register int j=l; j<=r; j++) {
dp[i&1][j+T] = max(dp[i&1][j+T], dp[i&1^1][j+T]);
dp[i&1][j+T] = max(dp[i&1][j+T], dp[i&1^1][j–v+T]+w);
}
}
printf("%d\\n", dp[N&1][T]);
return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容