T3892 : 产生至少 K 个峰值的最少操作次数

【江昊中 数学科学学院】做了力扣周赛, 周赛第四题除了用 dp , 问了 ai 后还学习到了反悔贪心的算法

dp, greedy with regret, https://leetcode.cn/problems/minimum-operations-to-achieve-at-least-k-peaks/

class Solution {
public:
    int minOperations(vector<int>& nums, int k) {
        const int n = nums.size();
        if (k > n / 2) return -1;

        // 使用两个数组 prev 和 next 来模拟双向链表
        vector<int> prev(n), next(n);
        for (int i = 0; i < n; i++) {
            prev[i] = (i + n - 1) % n;
            next[i] = (i + 1) % n;
        }

        vector<int> cost(n);
        for (int i = 0; i < n; i++) {
            int prev_val = nums[prev[i]];
            int next_val = nums[next[i]];
            cost[i] = max(0, max(prev_val, next_val) + 1 - nums[i]);
        }

        // 最小堆, 存放 {代价, idx}
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
        for (int i = 0; i < n; i++) {
            pq.push({cost[i], i});
        }

        vector<bool> visited(n, false);
        int ans = 0;

        // 贪心选取 k 次
        for (int i = 0; i < k; i++) {
            // 跳过已经被删除的节点
            while (!pq.empty() && visited[pq.top().second]) {
                pq.pop();
            }

            auto [val, idx] = pq.top();
            pq.pop();

            ans += val;
            int l = prev[idx], r = next[idx];
            visited[l] = visited[r] = true;

            // 将具有反悔代价的节点加入优先队列
            // 逻辑上等价于放弃当前节点 idx, 转而选取 l 和 r
            cost[idx] = cost[l] + cost[r] - val;
            pq.push({cost[idx], idx});

            // 在链表中删除 l 和 r
            prev[idx] = prev[l];
            next[idx] = next[r];
            next[prev[l]] = idx;
            prev[next[r]] = idx;
        }
        return ans;
    }
};

【姚博骞 物理学院】思路：循环条件下的“打家劫舍”，打家劫舍说的是不可以拿相邻的元素，这个题贪心地想，你没有必要对相邻地两个元素同时进行操作，因为相邻地两个元素最多只有一个峰。所以就变成了每个位置为了变成峰最小的增加数，用dp数组自底向上动态规划，记录遍历到点i处有j个峰的最小操作数dp[i][j],转移方程为：

$$a=max(max(nums[(i+n+1)\mathrm{\%}n],nums[(i+n-1)\mathrm{\%}n]),0)$$$$dp[i][j]=min(dp[(i+n-1)\mathrm{\%}n][j],dp[(i+n-2)\mathrm{\%}n][j-1]+a);$$

其中a是使得这个位置是峰的最小增加数。 这里用取模避免了对越界的讨论。 由于数组是环形的，有必要两个方向都做一遍然后取小者。 总体还是很好的一个dp练习题

class Solution {
public:
    int minOperations(vector<int>& nums, int k){//和打家劫舍是几乎一样的，相邻的不可能都是都是峰。最好的情况只对非相邻的元素操作。
        int n=nums.size();
        vector<vector<int>>dp(n,vector<int>(k+1,100000000000));
        vector<vector<int>>dp2(n,vector<int>(k+1,100000000000));
        for(int i=0;i<n;i++){
            dp[i][0]=dp2[i][0]=0;
        }
        if(k>nums.size()/2){
            return -1;
        }
        for(int i=0;i<n-1;i++){
            int a=max(max(nums[(i+n+1)%n],nums[(i+n-1)%n])+1-nums[i],0);
            for(int j=1;j<k+1;j++)
            {
                dp[i][j]=min(dp[(i+n-1)%n][j],dp[(i+n-2)%n][j-1]+a);
            }
        }
        for(int i=n-1;i>0;i--){
            int a=max(max(nums[(i+n+1)%n],nums[(i+n-1)%n])+1-nums[i],0);
            for(int j=1;j<k+1;j++)
            {
                dp2[i][j]=min(dp2[(i+n+1)%n][j],dp2[(i+n+2)%n][j-1]+a);
            }
        }
        return min(dp[n-2][k],dp2[1][k]);
    }
};