[Spe]朋友
【题目背景】
朋友?哼,有些人终成不了朋友;而朋友,真的只是时期段的吗?
【题目描述】
因比赛题目特设此题:
对于给定一个长度为 \(n\) 的序列 \(A\)(\(a_1,a_2...a_n\),首尾相连),求选择若干个不相邻数且必须选择 \(a_i\) 的情况下,所选数的和最大为多少 \(sum_i\)。(\(i∈[1,n]\))
【输入格式】
第一行一个数 \(n\)。
第二行 \(n\) 个数,为 \(a_i\)。
【输出格式】
共 \(n\) 行,每行一个数,为 \(sum_i\)。
【样例输入1】
3
-1 0 1
【样例输出1】
-1
0
1
【样例输入2】
6
-1 1 -1 -1 1 -1
【样例输出2】
0
2
0
0
2
0
【样例输入3】
7
1 2 3 4 5 6 7
【样例输出3】
11
14
15
13
15
12
15
【提示/说明】
时空限制:\(2s\),\(256MiB\)。
测试点序号 | \(n\) | \(\lvert a_{i}\rvert\) | 特殊性质 |
---|---|---|---|
\(1\sim 2\) | \(\leq 7\) | \(\leq 10\) | \(N\) |
\(3\sim 4\) | \(\leq 3*10^3\) | \(\leq 10^5\) | \(N\) |
\(5\sim 7\) | \(\leq 2*10^5\) | \(\leq 10^8\) | \(Y\) |
\(8\sim 10\) | \(\leq 2*10^6\) | \(\leq 10^8\) | \(N\) |
特殊性质:
\(N\):没有任何特殊性质。
\(Y\):对于 \(i∈[1,n]\),\(a_i\geq 0\)。
对于 \(100\%\) 的数据,\(3\leq n\leq 2*10^6\),\(-10^8\leq a_i\leq 10^8\)。
信息
- ID
- 1004
- 难度
- 9
- 分类
- (无)
- 标签
- (无)
- 递交数
- 6
- 已通过
- 1
- 通过率
- 17%
- 上传者