打卡信奥刷题（3270）用C++实现信奥题 P8848 [JRKSJ R5] 1-1 B

P8848 [JRKSJ R5] 1-1 B

题目背景

本题是 1-1 的较难版本，较易版本为 1-1 A。

题目描述

给出一个序列a aa，∀ i ∈ [ 1 , n ] , a i ∈ { 1 , − 1 } \forall i\in [1,n],a_i\in \{1,-1\}∀i∈[1,n],ai​∈{1,−1}。

询问有多少个将a aa重排后的序列使得该序列的最大子段和最小化。

称两个序列不同，当且仅当这两个序列有任意一个位置上的数不同。

输入格式

第一行一个整数n nn。

第二行n nn个整数表示a aa。

输出格式

一个整数表示答案。答案对998244353 998244353998244353取模。

输入输出样例 #1

输入 #1

4 1 -1 1 -1

输出 #1

3

输入输出样例 #2

输入 #2

5 1 1 1 -1 1

输出 #2

3

输入输出样例 #3

输入 #3

10 1 1 1 1 1 1 1 -1 -1 -1

输出 #3

40

说明/提示

最大子段和的定义：序列中一段区间的和的最大值。即max ⁡ 1 ≤ l ≤ r ≤ n ∑ i = l r a i \max_{1\le l\le r\le n} \sum_{i=l}^r a_imax1≤l≤r≤n​∑i=lr​ai​。

数据规模

本题采用捆绑测试。

对于100 % 100\%100%的数据，1 ≤ n ≤ 10 4 1\le n\le 10^41≤n≤104，a i ∈ { 1 , − 1 } a_i\in \{1,-1\}ai​∈{1,−1}。

C++实现

#include<bits/stdc++.h>usingnamespacestd;constintN=10086;constintmod=998244353;typedeflonglongll;intn,cp=0,cq=0;vector<int>a[N];signedmain(){intx;scanf("%d",&n);for(inti=1;i<=n;i++)scanf("%d",&x),x==1?cp++:cq++;intm=cp-cq;if(m>0){for(inti=0;i<=cq;i++)for(intj=0;j<=m;j++){ints=0;if(i&&j!=m)s+=a[i-1][j+1];if(j)s+=a[i][j-1];a[i].push_back(i||j?s%mod:1);}printf("%d",a[cq][m]);}else{for(inti=0;i<=1-m;i++)for(intj=0;j<=cp;j++){ints=0;if(i)s+=a[i-1][j];if(j)s+=a[i][j-1];a[i].push_back(i||j?s%mod:1);}printf("%d",a[1-m][cp]);}return0;}

后续

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