P8590 『JROI-8』这是新历的朝阳，也是旧历的残阳

题目背景

少女于海边伫立，凝视着落日最后的余晖
“已然过去了呢，旧历的一年…”

已获得转载授权。

题目描述

给定序列 {an}\{a_n\}{an​}，满足每一项都不小于前一项。对于所有不超过 $k$ 的正整数 $m$，询问如果将 $a$ 分成 $m$ 段（可以有空段），并给从前往后第 $i$ 段内的每个数都加上 $i$，增加后的 $\sum _{j=1}^n{a}_j^2$ 最大是多少。询问相互独立，即每次询问时给每个数加的值不保留到下一次询问。

例如，对于序列 {−3,1,2,2}\{-3,1,2,2\}{−3,1,2,2}，若 $m=5$，则一种分段方式是 $[-3][][1,2][][2]$，增加后的序列是 $-2,4,5,7$，此时 $\sum _{j=1}^n{a}_j^2=94$。

记 $m=i$ 时的答案（即此时最大的 $\sum _{j=1}^n{a}_j^2$）为 $q_i$，出于良心考虑，你只需要输出 $\left(\sum _{i=1}^k{q}_i\right)\mathrm{mod}998244353$ 即可。标准程序不基于特殊的输出方式，即能独立求出每一个 $q_i$。

输入格式

第一行两个正整数 $n,k$，同题意。

接下来一行 $n$ 个整数，表示 {an}\{a_n\}{an​}。

输出格式

一行一个整数，表示 $\left(\sum _{i=1}^k{q}_i\right)\mathrm{mod}998244353$。

输入输出样例 #1

输入 #1

4 3
-3 1 2 2

输出 #1

141

说明/提示

【样例解释】

当 $m=1$ 时，最优策略是 $[-3,1,2,2]$，$q_1=(-2{)}^2+2^2+3^2+3^2=26$。

当 $m=2$ 时，最优策略是 $[-3][1,2,2]$，$q_2=(-2{)}^2+3^2+4^2+4^2=45$。

当 $m=3$ 时，最优策略是 $[-3][][1,2,2]$，$q_3=(-2{)}^2+4^2+5^2+5^2=70$。

则 $\left(\sum _{i=1}^k{q}_i\right)\mathrm{mod}998244353=(q_1+q_2+q_3)\mathrm{mod}998244353=(26+45+70)\mathrm{mod}998244353=141$。

【数据范围与约束】

C++实现

#include<bits/stdc++.h>
#define XD 114514

using namespace std;
int n,k;
const int mod=998244353;
long long a[1000010],ans;
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
	} 
	for(int i=1;i<=k;i++){
		for(int j=1;j<=n;j++){
			if(abs(a[j]+1)>abs(a[j]+i)){//判断放最左面还是最右面
				ans+=(a[j]+1)*(a[j]+1);
				ans%=mod;
			}else{
				ans+=(a[j]+i)*(a[j]+i);
				ans%=mod;
			}
		}
	}
	cout<<ans;
	return 0;
}

后续

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