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

7个月前 (08-14)牛客题解254

一、题目解读

这道题目要求我们处理一组元素，每个元素属于一个集合(set)并有一个分值(value)。我们需要从中选择一个子序列，满足：

子序列中相邻元素属于相同集合时获得10分奖励
最终得分为元素分值总和加上所有相邻相同集合的奖励
在获得最大得分的同时，要求子序列长度最短

这是一个典型的动态规划问题，需要同时考虑得分最大化和序列长度最小化两个目标。

二、解题思路

本解法采用动态规划策略，核心思路如下：

定义DP[i][j]表示前i个元素中以集合j结尾的子序列的最大得分和对应最小长度
对于每个元素，考虑三种情况：

不选当前元素，直接继承前一个状态
选当前元素作为子序列的第一个元素
选当前元素作为子序列的非第一个元素，需要考虑与前一个元素的集合关系

最终遍历所有可能的结尾集合，找出最大得分及对应的最小长度

三、解题步骤

初始化：读取输入数据，定义元素结构体
初始化DP数组：dp[i][j]初始值为INT_MIN，表示不可达状态
处理第一个元素：初始化所有可能的状态起点
状态转移：

不选当前元素的情况
选当前元素作为子序列开头的情况
选当前元素作为子序列延续的情况（考虑集合相同奖励）

结果提取：遍历所有可能的结尾状态，找出最大得分和最小长度
输出结果

四、完整代码及注释

#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;
}