D. Learning to Paint

题意

有一个 $n$ 个格子长度的条带，格子从左到右编号为 $1\to n$，可以选择若干子段（或不选）的格子，给定一个二维数组 $a$
每选择一个 $[l_i,r_i]$ 子段，获得的价值 是 $a[l_i][r_i]$

问任意选择方案中，前 $k$ 大的价值是多少？（输出 $k$ 个价值）

思路

如果我们在当前位置 $i$ 枚举最后一个选择的区间 $[l,r]$，那么很显然我们 $1\to i$ 的前 $k$ 大可以从 $1\to (l-2)$ 转移过来，这里是一个 子状态

考虑 $DP$，我们定义 $d{p}_i$ 为 $[1,i]$ 的所有选择方案中，前 $min(2^i,k)$ 大的价值，并且将这些价值按非递增排列，那么在我们枚举最后一个区间时，我们可以从 $dp[l-2]$ 转移过来，$l-1$ 不能选是因为选了之后会和最后一个区间并上，那么最后一个区间就不是 $[l,i]$ 而是 $[l-1,i]$ 了

如果我们在每个位置 $i$，枚举最后一个区间，暴力转移，复杂度可达 $O(n^2\cdot k\log k)$

我们进一步观察发现，只需要选 $min(2^i,k)$ 个，其他很多价值都是多余的，并且每个位置 $dp[j]$ 的价值都是非递增排列，要选到后面的价值，前面的价值必须都要被选到！

这里就类似 $BFS$，我们只需要先将每个位置最大的价值加上对应的最后一个区间的 权重 放入优先队列，每次出队一个最大的价值，加入 $dp[i]$ 中，并将相应位置 $dp[j]$ 的下一个最大的价值入队，这样子一直处理到 $dp[i]$ 有 $k$ 个元素，或者前面位置没有元素可供转移为止

时间复杂度：$O(n\cdot (n+k)\cdot \log k)$
每个位置先将前 $i$ 个位置最大值入队，然后出队 $k$ 个元素

#include<bits/stdc++.h>
#define fore(i,l,r)	for(int i=(int)(l);i<(int)(r);++i)
#define fi first
#define se second
#define endl '\n'
#define ull unsigned long long
#define ALL(v) v.begin(), v.end()
#define Debug(x, ed) std::cerr << #x << " = " << x << ed;

const int INF=0x3f3f3f3f;
const long long INFLL=1e18;

typedef long long ll;

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int t;
    std::cin >> t;
    while(t--){
        int n, k;
        std::cin >> n >> k;
        std::vector<std::vector<int>> a(n + 1, std::vector<int>(n + 1, 0));
        fore(i, 1, n + 1)
            fore(j, i, n + 1)
                std::cin >> a[i][j];
        std::vector<std::vector<int>> dp(n + 1, std::vector<int>());
        dp[0] = {0};
        
        fore(i, 1, n + 1){
            std::priority_queue<std::array<int, 3>> q; //value index rank
            q.push({dp[i - 1][0], i - 1, 0}); //i 不选
            fore(j, -1, i - 1) q.push({(j < 0 ? 0 : dp[j][0]) + a[j + 2][i], j, 0}); //负数防止越界

            while(!q.empty() && dp[i].size() < k){  //保证不超过k个值的同时，前面选择方案还有可选
                auto [v, idx, rk] = q.top();
                q.pop();
                dp[i].push_back(v);
                if(idx < 0 || rk + 1 == dp[idx].size()) continue;
                if(idx == i - 1) q.push({dp[idx][rk + 1], idx, rk + 1});
                else q.push({dp[idx][rk + 1] + a[idx + 2][i], idx, rk + 1});
            }
        }

        for(auto v : dp[n]) std::cout << v << ' ';
        std::cout << endl;
    }
    return 0;
}