方法思路

这个问题类似于动态规划中的“打家劫舍”问题，但需要处理相邻灯的颜色不同这一额外约束。我们可以使用动态规划来解决，其中状态表示当前灯点亮蓝色或黄色时的最大得分，或者不点亮当前灯时的最大得分。

1. 状态定义：
   • dp[i][0]：表示第i盏灯不点亮时的最大得分。
   • dp[i][1]：表示第i盏灯点亮蓝色时的最大得分。
   • dp[i][2]：表示第i盏灯点亮黄色时的最大得分。
2. 状态转移：
   • 如果不点亮第i盏灯，那么前一个灯可以是任意状态。
   • 如果点亮第i盏灯为蓝色，那么前一个灯不能点亮蓝色。
   • 如果点亮第i盏灯为黄色，那么前一个灯不能点亮黄色。
3. 初始化：
   • 第一盏灯可以选择点亮蓝色或黄色，或者不点亮。
4. 结果计算：
   • 最终结果是最后一盏灯三种状态中的最大值。

代码实现

Java

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        long[][] dp = new long[n][3];
        int[][] scores = new int[n][2];
        
        for (int i = 0; i < n; i++) {
            String[] parts = br.readLine().split(" ");
            scores[i][0] = Integer.parseInt(parts[0]);
            scores[i][1] = Integer.parseInt(parts[1]);
        }
        
        dp[0][0] = 0;
        dp[0][1] = scores[0][0];
        dp[0][2] = scores[0][1];
        
        for (int i = 1; i < n; i++) {
            dp[i][0] = Math.max(dp[i-1][0], Math.max(dp[i-1][1], dp[i-1][2]));
            dp[i][1] = scores[i][0] + Math.max(dp[i-1][0], dp[i-1][2]);
            dp[i][2] = scores[i][1] + Math.max(dp[i-1][0], dp[i-1][1]);
        }
        
        long maxScore = Math.max(dp[n-1][0], Math.max(dp[n-1][1], dp[n-1][2]));
        System.out.println(maxScore);
    }
}

Python

import sys

def main():
    input = sys.stdin.read().split()
    ptr = 0
    n = int(input[ptr])
    ptr += 1
    scores = []
    for _ in range(n):
        x = int(input[ptr])
        y = int(input[ptr + 1])
        scores.append((x, y))
        ptr += 2
    
    dp = [[0] * 3 for _ in range(n)]
    dp[0][0] = 0
    dp[0][1] = scores[0][0]
    dp[0][2] = scores[0][1]
    
    for i in range(1, n):
        dp[i][0] = max(dp[i-1][0], dp[i-1][1], dp[i-1][2])
        dp[i][1] = scores[i][0] + max(dp[i-1][0], dp[i-1][2])
        dp[i][2] = scores[i][1] + max(dp[i-1][0], dp[i-1][1])
    
    print(max(dp[-1][0], dp[-1][1], dp[-1][2]))

if __name__ == "__main__":
    main()

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n;
    cin >> n;
    vector<pair<int, int>> scores(n);
    for (int i = 0; i < n; i++) {
        cin >> scores[i].first >> scores[i].second;
    }
    
    vector<vector<long long>> dp(n, vector<long long>(3));
    dp[0][0] = 0;
    dp[0][1] = scores[0].first;
    dp[0][2] = scores[0].second;
    
    for (int i = 1; i < n; i++) {
        dp[i][0] = max({dp[i-1][0], dp[i-1][1], dp[i-1][2]});
        dp[i][1] = scores[i].first + max(dp[i-1][0], dp[i-1][2]);
        dp[i][2] = scores[i].second + max(dp[i-1][0], dp[i-1][1]);
    }
    
    cout << max({dp[n-1][0], dp[n-1][1], dp[n-1][2]}) << endl;
    
    return 0;
}