当前位置：首页 > 牛客 > 牛客网23954题：动态规划解决队列得分

牛客网23954题：动态规划解决队列得分

8小时前

一、题目解读

本题考察动态规划在集合元素选择问题中的应用。题目给定N个元素，每个元素属于特定集合(set)并具有特定值(value)。要求选择若干元素组成序列，满足相邻元素若属于相同集合则扣除10分，最终目标是获得最高总分并使用最少元素。

二、解题思路

采用动态规划解法，定义dp[i][j]表示前i个元素中以集合j结尾时的最大得分和对应最小长度。通过三种状态转移处理：不选当前元素、选作第一个元素、选作后续元素。特别处理相邻相同集合的扣分情况。

三、解题步骤

1.初始化dp数组为INT_MIN

2.处理第一个元素的初始状态

3.遍历后续元素：

保持不选当前元素的状态

作为新序列开头的情况

作为序列延续的情况（处理集合相同扣分）

4.最终遍历所有集合状态找出最优解

四、完整代码实现

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

struct Element {
    int set;
    int value;
};

int main() {
    int N;
    cin >> N;
    vector<Element> elements(N);
    
    for (int i = 0; i < N; ++i) {
        cin >> elements[i].set >> elements[i].value;
    }
    
    // dp[i][j]表示前i个元素中以set j结尾的最大得分和最小长度
    vector<vector<pair<int, int>>> dp(N, vector<pair<int, int>>(21, {INT_MIN, 0}));
    
    // 初始化第一个元素
    dp[0][elements[0].set] = {elements[0].value, 1};
    
    for (int i = 1; i < N; ++i) {
        int current_set = elements[i].set;
        int current_value = elements[i].value;
        
        // 不选当前元素的情况
        for (int j = 1; j <= 20; ++j) {
            dp[i][j] = dp[i-1][j];
        }
        
        // 选当前元素作为第一个元素
        if (current_value > dp[i][current_set].first) {
            dp[i][current_set] = {current_value, 1};
        } else if (current_value == dp[i][current_set].first) {
            dp[i][current_set].second = min(dp[i][current_set].second, 1);
        }
        
        // 选当前元素作为非第一个元素
        for (int prev_set = 1; prev_set <= 20; ++prev_set) {
            if (dp[i-1][prev_set].first == INT_MIN) continue;
            
            int bonus = (prev_set == current_set) ? 10 : 0;
            int new_score = dp[i-1][prev_set].first + current_value - bonus;
            int new_length = dp[i-1][prev_set].second + 1;
            
            if (new_score > dp[i][current_set].first) {
                dp[i][current_set] = {new_score, new_length};
            } else if (new_score == dp[i][current_set].first) {
                dp[i][current_set].second = min(dp[i][current_set].second, new_length);
            }
        }
    }
    
    // 找出所有可能的最大得分
    int max_score = INT_MIN;
    int min_length = INT_MAX;
    
    for (int j = 1; j <= 20; ++j) {
        if (dp[N-1][j].first > max_score) {
            max_score = dp[N-1][j].first;
            min_length = dp[N-1][j].second;
        } else if (dp[N-1][j].first == max_score) {
            min_length = min(min_length, dp[N-1][j].second);
        }
    }
    
    cout << max_score << " " << min_length << endl;
    return 0;
}