环上最大独立集

题目描述

给出一个有 $n$ 个点的环，每个点有点权 $a_i$，求满足点集内任何两个点在环上不相邻，且点权和最大的点集的点权和。
注意点 $1$ 和 点 $n$ 是相邻的。

输入格式

第一行输入一个正整数 $n$，表示点的数目。
第二行输入 $n$ 个以空格隔开的整数，依次表示各个点的点权 $a_i$。

输出格式

输出一行一个整数，表示求得的最大点权和。

样例 #1

样例输入 #1

7
2 -2 8 6 -1 -5 5

样例输出 #1

13

提示

对于 $50\%$ 的数据满足 $n\le 18$；
对于 $100\%$ 的数据满足 $2\le n\le 10^5,|a_i|\le 10^9$。

解题方法

若不考虑环，此题的转移方程如下：

$$f[i][1]=f[i-1][0]$$
$$f[i][0]=max\{f[i-1][1],f[i-1][0]\}$$

其中 $f[i][1]$ 代表第 $i$ 个元素要取，$f[i][0]$ 代表第 $i$ 个元素不取。若第 $i$ 个元素要取，则第 $i-1$ 个元素不能取。若第 $i$ 个元素不取，则第 $i-1$ 个元素可取可不取。以上便是转移方程的由来。

若按照传统的化环成链方法，时间复杂度为 $O(n^2)$ 很明显不能通过本题，但是我们可以从这个方法展开思考。为什么要化环成链？因为在环里，$1$ 号元素和 $n$ 号元素是靠在一起的，若 $1$ 取，则 $n$ 号元素不能取，反之亦然。我们就可以分情况进行动态规划，第一种情况是当 $1$ 号元素不取的时， $n$ 号元素可取可不取。第二种情况是当第 $n$ 号元素取时，则 $1$ 号元素可取可不取。

为了达到此目的，情况一我们可以将 $f[1][0]$ 的值设为 $-\infty$ ，情况二可以将 $f[1][1]$ 的值设为 $-\infty$。接着进行上述动态规划，问题即可迎刃而解。

AC 代码