开始的时候看错题了。以为区间是可以我划分的，后面才发现是连着的区域是被强制合并的。
导致我第一个写了给k短路。紫砂了。
然后我的第二个思路是，从后往前和从前往后做两边dp，然后尝试枚举断点，看看有没有比最优稍微劣一点的解法。
然后样例就是反例。
正解是想到过的，但是因为时间复杂度被叉了。我觉得这个k和n应该是不能被同时记录在dp中的，然后就产生了上面的做法中的贪心，也就是前k短路应该都是由最短路改变而来的。
不然在我的认知里面，这题不可做。然后就wa在了test1。没过样例。
妈妈生的，为什么会觉得记录前k个答案会T啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊
我在想什么。
正解就是设\(f[i]\)表示以\(i\)结尾（\(i\)不选）的前面的区间能够取到的前k个最大的答案。
然后转移其实就很简单，每次考虑前面的位置，先把每个位置\(f[j]\)的 第一个数字放入优先队列里面，然后就取里面最大的放到\(f[i]\)中，再把这个\(f[j]\)的下个位置入队。
满了k个就结束。
\(O((n+k)\times n \times log(nk))\)
很可以做啊。。。。
为什么。。我会把这个记录前k个答案的方法叉了。。
为什么。。。。
唉唉
可能因为前面没有做过类似的题目吧。。。
难绷。这真是太蠢了。。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline int read() {
char c=getchar();int a=0,b=1;
for(;c<'0'||c>'9';c=getchar())if(c=='-')b=-1;
for(;c>='0'&&c<='9';c=getchar())a=a*10+c-48;return a*b;
}
int n,k,a[1001][1001];
vector<int> dp[1001];
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
int T=read();
while(T--)
{
n=read();k=read();
for(int i=1;i<=n;i++)
{
for(int j=i;j<=n;j++)
{
a[i][j]=read();
}
}
for(int i=0;i<=n;i++)
{
dp[i].clear();
}
dp[0].push_back(0);
for(int i=1;i<=n;i++)
{
priority_queue<pair<int,pair<int,int> > > q;
q.push({dp[i-1][0],{i-1,0}});
for(int j=i-2;j>=0;j--)
{
q.push({dp[j][0]+a[j+2][i],{j,0}});
}
q.push({0+a[1][i],{-1,0}});
while(q.size()!=0 && dp[i].size()<k)
{
int val=q.top().first;
int j=q.top().second.first;
int num=q.top().second.second;
q.pop();
dp[i].push_back({val});
if(j<0||num+1==dp[j].size())continue;
if(j==i-1)//Needn't create interval
{
q.push({dp[j][num+1],{j,num+1}});
}
else
{
q.push({dp[j][num+1]+a[j+2][i],{j,num+1}});
}
}
}
for(int i=0;i<k;i++)
{
cout<<dp[n][i]<<' ';
}
cout<<endl;
}
return 0;
}