CF1942 D. Learning to Paint [求topk的dp]

本文主要是介绍CF1942 D. Learning to Paint [求topk的dp]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门:CF

[前题提要]:赛时想不到怎么维护topk的方法,掉大分了.赛后发现该维护方法应该算一个挺典的trick,故记录一下

---

首先对于这道题,我们发现显然是需要使用dp,因为我们需要在最后输出前$k$大的贡献,然后$n$范围才$1e3$,这一切都在暗示我们使用dp.
考虑如何使用dp,其实不难想到使用$dp[i][k][0/1]$来记录前i个位置,最后一段染色的位置是否在第$i$位的第$k$大贡献.
先考虑最后一段染色的位置在第$i$位我们该如何进行递推
不难发现我们需要枚举每一个位置,还需要枚举最后一段染色区间的左端点,然后还需要维护k次,所以我们需要的复杂度是$n\ast n\ast k$的,并且还需要这么大的空间,显然发现很难维护.此时需要插播一个维护$topk$的经典方法(引用一个up主的举例).

---

先来考虑一个经典问题:对于两个长度为$n$($n$是$1e5$级别)的数组$a,b$,我们可以挑选$a,b$中的任意位置的数字(但是$<i,j>$只能选一次),将其相加,形成一个新的序列,对于新生成的序列,问第$k$大($k$是$1e5$级别)是多少?

显然我们新的序列的长度是$n^2$的,无法直接维护.但是我们发现$k$不大,借机我们会发现大多数的数字都是没用的.首先我们将两个数组进行从大到小排序,$top1$显然就是$a[1]+b[1]$.那么$top2$是什么呢,我们会发现是$max(a[2]+b[1],a[1]+b[2])$,那么假设我们选了其中的一个数字,$top3$又是哪个呢?更形象的来说,当我们对于a,b列出一个二维表,我们会发现当你取出了一个数之后,这个数右边和下面的数字才有可能成为新的最大值.因为对于每一个数来说,如果该数可能成为最大值,该数左边和上面的数字必然全部都被选出才有可能.然后我们可以使用$set$或者$priority\_queue$来维护这个东西了,每次取出最大值作为topi,然后对于该数,我们加入该数下面和右边的数

---

类似的,我们也可以使用上述这种延时加入的方法来维护本题.对于本题,我们会发现同样存在上述这种优先级关系.对于$dp[i][k][0/1]$来说,他想成为新的贡献值,那么必然要选取$k$之前的所有数.所以我们同样可以使用优先队列来维护$topk$.先考虑加入所有$dp[i\in [1,now-1]][1]$,然后取出一个$dp[j][1]$之后再加入$dp[j][2]$…

对于最后一段染色区间的右端点不在当前枚举区间的情况,此时now位置没有贡献,所以直接取$dp[now][k][0/1]$的前$k$大即可.

---

下面是具体的代码部分:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls (rt<<1)
#define rs (rt<<1|1)
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {ll x=0,w=1;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';return x*w;
}
inline void print(__int128 x){if(x<0) {putchar('-');x=-x;}if(x>9) print(x/10);putchar(x%10+'0');
}
#define maxn 1000000
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
int a[1010][1010];
int dp[1010][5010][2];
//dp[i][j][0/1]表示前i个位置最后一段的端点是否在第i个位置的第j大的值
struct Node{int pos,rank,val;bool operator < (const Node &rhs) const {return val<rhs.val;}
};
int main() {int T=read();while(T--) {int n=read();int 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++) {for(int j=1;j<=k;j++) {dp[i][j][0]=dp[i][j][1]=-int_INF;}}dp[0][1][0]=0;for(int i=1;i<=n;i++) {priority_queue<Node>q;for(int j=0;j<i;j++) {q.push({j,1,dp[j][1][0]+a[j+1][i]});}for(int j=1;j<=k;j++) {auto [pos,rank,val]=q.top();q.pop();dp[i][j][1]=val;q.push({pos,rank+1,dp[pos][rank+1][0]+a[pos+1][i]});}int pos1=1,pos2=1;for(int j=1;j<=k;j++) {if(dp[i-1][pos1][0]>dp[i-1][pos2][1]) {dp[i][j][0]=dp[i-1][pos1][0];pos1++;}else {dp[i][j][0]=dp[i-1][pos2][1];pos2++;}}}int pos1=1,pos2=1;for(int i=1;i<=k;i++) {if(dp[n][pos1][0]>dp[n][pos2][1]) {cout<<dp[n][pos1][0]<<" ";pos1++;}else {cout<<dp[n][pos2][1]<<" ";pos2++;}}cout<<endl;}	return 0;
}

这篇关于CF1942 D. Learning to Paint [求topk的dp]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---