专栏文章

题解：P7804 [JOI Open 2021] 决算报告 / Financial Report

EEchoHua0402
P7804题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min9rsji
此快照首次捕获于
2025/12/01 22:53
3 个月前
此快照最后确认于
2025/12/01 22:53
3 个月前
查看原文

题意

由于本题题面描述过于抽象，所以先来翻译一下题意。
给出一个长为 nn 的序列 AA，请你选出 AA 的一个子序列 pp ，要求子序列的相邻两项在原序列中的位置的差 ≤D\le D。定义一个子序列的收益是 ∑Ai∈p[Ai>Aj](Aj∈p,j<i)\sum\limits_{A_i \in p} [A_i > A_j] (A_j \in p, j<i) ，求最大收益。

做法

在下文中，称“关键元素”为在子序列中满足 [Ai>Aj](Aj∈p,j<i)[A_i > A_j] (A_j \in p, j<i) 的 AiA_i。
首先考虑设 dpidp_i 表示以第 ii 个元素为末个关键元素的子序列的最大收益值，那么转移即为 dpi=max⁡j<i,Aj<Aidpjdp_i=\max\limits_{j<i,A_j<A_i} dp_j。
现在考虑“相邻两项在原序列中的位置的差 ≤D\le D”这一限制该如何转化为判定合法的 jj 的条件。我们发现，“ii 和 jj 之间不存在一个所有元素均 ≥Ai\ge A_i 的连续段”是 jj 合法的充要条件。
证明省略，比较简单，读者可以尝试自己证一下。
通过进一步思考，发现合法的 jj 是连续的（不是真的连续，因为还有对 AjA_j 的大小限制，不过如果把 Aj<AiA_j<A_i 的所有 AjA_j 抽出来，合法的 jj 就是连续的了），这提示我们可以使用数据结构来优化 dpdp。
为了“去除”掉大小的限制，我们先按 AiA_i 从小到大排序（如果 Ai=AjA_i=A_j，则位置靠后的更小），这样后面的转移就可以不考虑大小了，因为所有已经被更新过的 dpjdp_j 均有 Aj<AiA_j<A_i。
可以弄一个 set 用来维护已经更新过的 dpjdp_j 的下标。设 kk 是 set 中 ii 的前一项，也就是 <i<i 的最大的已经更新过的位置，如果 i−k≤Di-k \le D 那么 kk 就是一个合法的转移点。转移点具有“传递性”，因为可以一个一个往前“跳”。所以我们维护一个并查集，ii 所在的集合的祖先就是 ii 可以往前跳到的下标最小的转移点。
于是我们就获得了做法：排序后，从小到大更新 dpdp 值，每次更新第 ii 个元素的时候，判一下 ii 前后两个位置与它的差是否 ≤D\le D，如果是则合并两个集合。所以 dpi=max⁡find(i)≤j<idpjdp_i=\max\limits_{\text{find(i)} \le j < i} dp_j，这个直接用线段树维护区间最大值即可，更新完 ii 后，更改其在线段树上的值即可。

代码

个人认为还是比较具有可读性的：
CPP
#include <bits/stdc++.h>
using namespace std;
const int N=3e5+5;
int n,D,ans=0,fa[N];
struct F{int x,id;}a[N];
bool cmp(F a,F b) {return a.x==b.x?a.id>b.id:a.x<b.x;}
struct Node{int l,r,mx;}tree[N<<2];
void pushup(int p) {tree[p].mx=max(tree[p*2].mx,tree[p*2+1].mx);}
void build(int p,int l,int r) {	
	tree[p].l=l,tree[p].r=r,tree[p].mx=0;
	if (l==r) return ;
	int mid=(l+r)>>1;
	build(p*2,l,mid); build(p*2+1,mid+1,r);
}
void modify(int p,int x,int k) {
	if (tree[p].l==tree[p].r) {tree[p].mx=max(tree[p].mx,k); return ;}
	int mid=(tree[p].l+tree[p].r)>>1;
	if (x<=mid) modify(p*2,x,k);
	else modify(p*2+1,x,k);
	pushup(p);
}
int query(int p,int l,int r) {
	if (l<=tree[p].l&&tree[p].r<=r) return tree[p].mx;
	int mid=(tree[p].l+tree[p].r)>>1,res=0;
	if (l<=mid) res=max(res,query(p*2,l,r));
	if (r>mid) res=max(res,query(p*2+1,l,r));
	return res;
}
inline int find(int x) {return x==fa[x]?x:fa[x]=find(fa[x]);}
inline void Merge(int u,int v) {
	int fu=find(u),fv=find(v);
	fa[max(fu,fv)]=min(fu,fv);
}
int main() {
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>D; build(1,1,n);
	for (int i=1;i<=n;i++) cin>>a[i].x,a[i].id=i,fa[i]=i;
	sort(a+1,a+n+1,cmp); set<int> now;
	for (int i=1;i<=n;i++) {
		int id=a[i].id; now.insert(id);
		auto p=now.find(id);
		int lst=(p!=now.begin()?(*prev(p)):-1),nxt=(next(p)!=now.end()?(*next(p)):-1);
		if (lst!=-1&&id-lst<=D) Merge(lst,id);
		if (nxt!=-1&&nxt-id<=D) Merge(id,nxt);
		int dp=query(1,find(id),id)+1; ans=max(ans,dp);
		modify(1,id,dp);
	}
	cout<<ans<<"\n";
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...