专栏文章

题解：P1982 [NOIP2013 普及组] 小朋友的数字

QQfaiser
P1982题解参与者 3已保存评论 4

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
4 条
当前快照
1 份
快照标识符
@miqjmiio
此快照首次捕获于
2025/12/04 05:52
3 个月前
此快照最后确认于
2025/12/04 05:52
3 个月前
查看原文

solution

动态规划问题。
设 aia_i 表示 ii 的数字，qiq_i 表示以 ii 结尾的最大子段和，初始化 q1=a1q_1=a_1，转移 qi=max⁡(ai,qi−1+ai)q_i = \max(a_i, q_{i-1}+a_i)。
设 tit_i 表示前 ii 个数中以任意数结尾的最大子段和，也是 ii 的特征值，初始化 t1=a1t_1=a_1，则 ti=max⁡(ti−1,qi)t_i = \max(t_{i-1}, q_i)。
设 fif_i 表示 ii 的分数，题目说第一个人的分数是第一个人的特征值，故初始化 f1=t1f_1=t_1，考虑转移。
对于 ii 的分数，可以是前 i−2i-2 个人中分数加上其特征值的最大值，也就是第 i−1i-1 个人的分数，即 fi−1f_{i-1}，也可以是第 i−1i-1 个人的分数加上其特征值，即 fi−1+tif_{i-1}+t_i，fi=max⁡(fi−1,fi−1+ti−1)f_i = \max(f_{i-1}, f_{i-1}+t_{i-1})。
这里要特判 f2=f1+t1f_2=f_1+t_1，否则可能会算成 f1f_1。
结果会很大，并且没办法随时取模，所以要开 __int128。

code

CPP
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
long long n, p, a[N], q[N], t[N];
__int128 f[N], ans;
void out (__int128 x) {
	if (x>9)
		out(x/10);
	putchar(x%10+'0');
}
int main () {
	cin >> n >> p;
	for (int i=1; i<=n; ++i)
		cin >> a[i];
	ans=f[1]=t[1]=q[1]=a[1];
	for (int i=2; i<=n; ++i)
		q[i]=max(q[i-1]+a[i], a[i]),
		t[i]=max(t[i-1], q[i]),
		f[i]=(i==2?2*f[1]:max(f[i-1], f[i-1]+t[i-1])),
		ans=max(ans, f[i]);
	if (ans<0)
		cout << '-',
		ans=-ans;
	out(ans%p);
	return 0;
}

评论

共 4 条评论，欢迎与作者交流。

正在加载评论...