6498: 圆环独立集
[Creator : ]
Description
给定一个长度为 $n$ 的环状数列 $a_1,a_2,\cdots, a_n$,请从这些数字中间挑选出一个独立集,使得独立集中的数字之和达到最大。
所谓环状,是指在考虑相邻关系时,需要把 $a_1$ 和 $a_n$ 也看做是一对邻居。所谓独立集,就是挑选出的数字在原来的圆环上不能相邻。
所谓环状,是指在考虑相邻关系时,需要把 $a_1$ 和 $a_n$ 也看做是一对邻居。所谓独立集,就是挑选出的数字在原来的圆环上不能相邻。
Input
第一行:单个整数表示 $n$。
第二行:$n$ 个整数表示 $a_1, a_2, \cdots, a_n$。
第二行:$n$ 个整数表示 $a_1, a_2, \cdots, a_n$。
Output
单个整数:表示最小的修改工作量。
Constraints
对于 $30\%$ 的数据,$1\leq n\leq 20$;
对于 $60\%$ 的数据,$1\leq n\leq 5000$;
对于 $100\%$ 的数据,$1\leq n\leq 500,000$,
$1\leq a_i\leq 1,000,000$。
对于 $60\%$ 的数据,$1\leq n\leq 5000$;
对于 $100\%$ 的数据,$1\leq n\leq 500,000$,
$1\leq a_i\leq 1,000,000$。
Sample 1 Input
5
1 1 8 7 2
Sample 1 Output
10
取 $8$ 和 $2$。$1,8,2$ 不可取,因为 $1$ 和 $2$ 是相邻的。
Sample 2 Input
6
100 1 1 100 1 1
Sample 2 Output
200
这个例子告诉我们最优独立集不一定是最大独立集