题解

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

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

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

状态转移为：

for(int t = 0; t < 3; t ++)
		for(int k = 0; k < 3; k ++)
			if(k != t)
				f[i][t] = max(f[i][t], f[i - 1][k]) + (对应的权值) // 只要上盏灯不和这盏灯状态相同即可转移

时间复杂度为 : $O(n)$

AC代码

• Cpp

#include<bits/stdc++.h>

using namespace std;

#define int long long


signed main (){
    ios::sync_with_stdio(false);
    std::cin.tie(0);
    int n; cin >> n;
    vector<vector<int>> a(n, vector<int>(2));
    for(int i = 0; i < n; i ++)
        cin >> a[i][0] >> a[i][1];
    vector<vector<int>> dp(n, vector<int>(3, -1));
    auto dfs = [&](auto dfs, int u, int c) -> int{
        if(u == n)
            return 0;
        if(dp[u][c] != -1)
            return dp[u][c];
        
        int res = dfs(dfs, u + 1, 0);
        if(c)
        {
            int r = 3 - c;
            res = max(dfs(dfs, u + 1, r) + a[u][r - 1], res);
        }
        else
        {
            res = max(res, dfs(dfs, u + 1, 1) + a[u][0]);
            res = max(res, dfs(dfs, u + 1, 2) + a[u][1]); 
        }
        dp[u][c] = res;
        return res; 
    };
    int res = dfs(dfs, 0, 0);
    cout << res << "\n";
    return 0;
}

• python

import sys
sys.setrecursionlimit(2000000)
def dfs(u, c):
    if u == n:
        return 0
    if dp[u][c] != -1:
        return dp[u][c]
    
    res = dfs(u + 1, 0)
    if c:
        r = 3 - c
        res = max(dfs(u + 1, r) + a[u][r - 1], res)
    else:
        res = max(res, dfs(u + 1, 1) + a[u][0])
        res = max(res, dfs(u + 1, 2) + a[u][1])
    
    dp[u][c] = res
    return res

n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
dp = [[-1] * 3 for _ in range(n)]
res = dfs(0, 0)
print(res)

• Java

import java.util.Scanner;

public class Main {
    static int n;
    static long[][] a;
    static long[][] dp;

    static long dfs(int u, int c) {
        if (u == n) return 0;
        if (dp[u][c] != -1) return dp[u][c];

        long res = dfs(u + 1, 0);
        if (c != 0) {
            int r = 3 - c;
            res = Math.max(dfs(u + 1, r) + a[u][r - 1], res);
        } else {
            res = Math.max(res, dfs(u + 1, 1) + a[u][0]);
            res = Math.max(res, dfs(u + 1, 2) + a[u][1]);
        }

        dp[u][c] = res;
        return res;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        a = new long[n][2];
        dp = new long[n][3];
        for (int i = 0; i < n; i++) {
            a[i][0] = scanner.nextLong();
            a[i][1] = scanner.nextLong();
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 3; j++) {
                dp[i][j] = -1;
            }
        }
        long res = dfs(0, 0);
        System.out.println(res);
    }
}

问题描述

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

输入格式

第一行包含一个正整数 $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$。