题解

简述一下题意，有 $n$ 盏灯，每个灯有两种颜色，每种颜色对应一个权值，可以选择一种颜色点亮，或者不点点，不能有两盏连续的灯颜色相同。

这题是 Leetcode上的 打家劫舍 变形题，是一类动态规划的问题。

定义 $f[i][j]$ 为，考虑前 $i$ 盏灯，且最后一盏灯的状态为 $j \quad j \in [0, 1, 2]$ 的最大权值。

状态转移为：

问题描述

小红的家乡即将举行一年一度的彩灯节。节日中，小红负责布置一排彩灯，每个彩灯可以选择亮起“红”或“绿”两种颜色，用红色代表喜庆，会增加喜气值；用绿色代表和谐，会增加安宁值。但是为了避免颜色单调，相邻的灯不能亮起相同的颜色。在确保相邻彩灯颜色不同的前提下，小红想知道如何点亮这些彩灯才能使得喜气值和安宁值的总和最大。

输入格式

第一行包含一个正整数 $n$，表示彩灯的总数。

接下来 $n$ 行，每行两个正整数 $r_i$ 和 $g_i$，分别表示第 $i$ 个彩灯亮起红色和绿色时所增加的喜气值和安宁值。

输出格式

输出一行一个整数，表示小红点亮彩灯后能获得的最大总和值。

样例输入

4
1 3
4 3
5 6
2 3

样例输出

15

评测数据与规模

• $1 \leq n \leq 10 ^ 5$，$1 \leq r_i, g_i \leq 10 ^ 9$。