首页 > 其他分享 >DP提高专项3

DP提高专项3

时间:2023-10-06 09:00:28浏览次数:36  
标签:专项 tag1 tag2 int 提高 MAXN DP dp mod

本场比赛难度吧不大,建议开题顺序为 \(T2-T1-T3\) 。

\(T2\)

题目描述

有 \(n\) 个高楼排成一行,每个楼有一个高度 \(h_i\)。称可以从楼 \(i\) 跳到 楼 \(j\),当 \(i\), \(j\) ( \(i < j\) )满足以下三个条件之一:

  • \(i+1=j\)

  • \(\max(h_{i+1},h_{i+2},\cdots,h_{j-1})<\min(h_i,h_j)\)

  • \(\min(h_{i+1},h_{i+2},\cdots,h_{j-1})>\max(h_i,h_j)\)

现在你在楼 \(1\),请求出跳到楼 \(n\) 最少要跳几次。

\(2 \leq n \leq 3\cdot 10^5\), \(1\leq h_i \leq 10^9\)。

思路点拨

没有什么思维的题。考虑动态规划,暴力转移显然是 $O(n^2) $ 的。

但是注意到条件 \(2,3\) 本质上是在描述序列的峰谷,我们知道这样的二元组 \((i,j)\) 的数量线性,所以使用单调栈求出。

时间复杂度线性。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=3e5+10;
int n,a[MAXN];
int f[MAXN];
int s1[MAXN],top1,s2[MAXN],top2;
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	s1[++top1]=s2[++top2]=1;
	for(int i=2;i<=n;i++){
		f[i]=f[i-1]+1;
		while(top1&&a[s1[top1]]<=a[i]){
			int tmp=a[s1[top1--]];
			if(a[i]!=tmp&&top1)
				f[i]=min(f[i],f[s1[top1]]+1);
		}
		while(top2&&a[s2[top2]]>=a[i]){
			int tmp=a[s2[top2--]];
			if(a[i]!=tmp&&top2)
				f[i]=min(f[i],f[s2[top2]]+1);
		}//找出全部峰谷 
		s1[++top1]=s2[++top2]=i;
	}
	cout<<f[n]; 
	return 0;
}

\(T1\)

题目描述

现在有一个长度为 \(n\) 的序列 \(a\) 和一个常数 \(c\) 。

我们希望将序列分成若干段,那么对于长度为 \(k\) 的一段,我们去除前 \(\lfloor \dfrac{k}{c}\rfloor\) 小的元素。

我们希望剩下的数尽量小。

\(n \leqslant 10^5\) 。

思路点拨

考虑转话题意,希望删除的数尽量大。那么我们知道,删除的数的数量相同的情况小,子段越长,那么最小值也就跟小。

所以说我们要选择长度为 \(1\) 的段,要么选择长度为 \(c\) 的段。

我们设 \(dp_i\) 表示考虑到下标 \(i\) ,剩下数的最大值,转移显然:

\[dp_i=\max\{dp_{i-1},dp_{i-c}+mx_{i-c+1,i}\} \]

发现 \(mx\) 是一个滑动窗口,所以用单调队列优化。

时间复杂度线性。

\(T3\)

题目描述

给你一个正整数序列 \(a_1,a_2,...a_n\),计算有多少个正整数序列 \(b_1,b_2,...b_n\),满足:

  1. \(1\le b_i \le a_i\),\(i\in [1,n]\)
  2. \(b_i\neq b_{i+1}\),\(i\in[1,n)\)

答案对 998244353 取模。

\(n \leqslant 10^5\) 。

思路点拨

当 \(n,a\) 都比较小的时候,有一个暴力 \(dp\) 的做法。

设 \(dp_{i,j}\) 表示考虑到第 \(i\) 个元素,这个值为 \(j\) 的方案,转移显然:

\[dp_{i,j}=\sum_{0<k \leqslant a_{i-1}} dp_{i-1,k}[j \neq k] \]

我们考虑使用数据结构优化这个过程。

我们的转移可以表述为:

\[dp_{i,j}=-dp_{i,j}+\sum_{0<k \leqslant a_{i-1}} dp_{i-1,k} \]

我们考虑将这个 \(dp\) 数组放进一个动态开点权值线段树里面。那么每一次我们从 \(dp_{i-1}\) 向 \(dp_i\) 转移的时候,我们可以:

  • 将全部的 \(dp\) 值取反

  • 加上原来权值线段树全部 \(dp\) 值得和

  • 将 \(dp_{i,j}(j>a_i)\) 的部分清空

在这个东西可以使用线段树2模板解决。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=2e5+10,mod=998244353;
const int N=1e9;
int n,a[MAXN];
int rot,tot;
struct node{
	int x,l,r;
	int tag1,tag2;//乘法标记,加法标记 
	node(){tag1=1;}
}t[MAXN*60];
void pushup(int i){
	t[i].x=(t[t[i].l].x+t[t[i].r].x)%mod;
} 
void pushdown(int i,int l,int r){
	int mid=(l+r)>>1;
	if(!t[i].l) t[i].l=++tot;
	if(!t[i].r) t[i].r=++tot;
	t[t[i].l].x=t[t[i].l].x*t[i].tag1%mod;
	t[t[i].r].x=t[t[i].r].x*t[i].tag1%mod;
	t[t[i].l].tag1=t[t[i].l].tag1*t[i].tag1%mod;
	t[t[i].r].tag1=t[t[i].r].tag1*t[i].tag1%mod;
	t[t[i].l].tag2=t[t[i].l].tag2*t[i].tag1%mod;
	t[t[i].r].tag2=t[t[i].r].tag2*t[i].tag1%mod;
	
	t[t[i].l].x=(t[t[i].l].x+(mid-l+1)*t[i].tag2)%mod;
	t[t[i].r].x=(t[t[i].r].x+(r-mid)*t[i].tag2)%mod;
	t[t[i].l].tag2=(t[t[i].l].tag2+t[i].tag2)%mod;
	t[t[i].r].tag2=(t[t[i].r].tag2+t[i].tag2)%mod;
	t[i].tag1=1,t[i].tag2=0;
}
void update(int &i,int l,int r,int L,int R,int w,int o){//区间加w(o=1)|区间乘w(o=2) 
	if(!i) i=++tot;
	pushdown(i,l,r);
	if(L<=l&&r<=R){
		if(o==1){
			t[i].x=(t[i].x+(r-l+1)*w)%mod;
			t[i].tag2=w;
		}
		else{
			t[i].x=t[i].x*w%mod;
			t[i].tag1=w;
		}
		return ; 
	}
	else if(l>R||r<L) return ;
	int mid=(l+r)>>1;
	update(t[i].l,l,mid,L,R,w,o);
	update(t[i].r,mid+1,r,L,R,w,o);
	pushup(i);
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	update(rot,1,N,1,a[1],1,1);//初始化dp[i<=a[1]]=1
	for(int i=2;i<=n;i++){
		int w=t[rot].x;//全体取反之后加上w
		update(rot,1,N,1,N,mod-1,0);
		update(rot,1,N,1,N,w,1);
		if(a[i]<N) update(rot,1,N,a[i]+1,N,0,0); 
	}
	cout<<t[rot].x; 
	return 0;
}

标签:专项,tag1,tag2,int,提高,MAXN,DP,dp,mod
From: https://www.cnblogs.com/Diavolo/p/17744238.html

相关文章

  • 【DP】ABC273F Hammer 2 题解
    ABC273F一道比较板的区间\(\text{dp}\)。先对坐标离散化,令离散化数组为\(v\)。令\(f_{i,j}\)表示能走到区间\([v_i,v_j]\)的最短路程,显然\(f\)数组初始为\(inf\)。但发现这样无法转移,可以再增加一维\(k\in\{0,1\}\),表示此时在\([v_i,v_j]\)的\(v_i/v_j\)处。......
  • 【思维】【DP】ABC298Ex Sum of Min of Length 题解
    ABC298Ex简单题。因为有\(\min\)不好做,容易想到讨论\(d(i,L)\)和\(d(i,R)\)的大小。令\(p=\text{LCA}(L,R)\),\(dep_L>dep_R,dist=dep_L+dep_R-2\timesdep_p\),\(now\)满足\(dep_L-dep_{now}=\lfloor\dfrac{dist}{2}\rfloor\)则\(L\)一定在......
  • 动态规划--DP
    动态规划动态规划是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。背包01背包每个物体只有两种可能的状态(取与不取),对应二进制中的\(0\)和\(1\),这类问题便被称为「0-1背包问题」。状态转移方程:\[f_{i,j}=\max(f_{i-1,j},f_{i-1,j-w_{i}}+v_{i})\]这......
  • 【竞赛图】【DP】ARC163D Sum of SCC 题解
    ARC163D发现这个竞赛图一定能被分为两个集合\(A\),\(B\)。满足\(\forallu\inA,v\inB\),均有\(u\tov\inE\)。答案就是划分这两个集合的方案数。证明:首先,竞赛图缩完点后一定是一条链,对强连通分量进行标号,满足编号小的强连通分量指向编号大的强连通分量。不妨令竞赛图\(G\)......
  • 【整除分块】【DP】ABC239Ex Dice Product 2 题解
    ABC239H简单题。令\(f_i\)表示乘到\(\gei\)的期望。容易得到\(f_i=\dfrac{\sum\limits_{j=1}^{n}f_{\lceil\frac{i}{j}\rceil}}{n}\)。将\(f_i\)移到同一边,去掉系数,有\(f_i=\dfrac{n\sum\limits_{j=2}^{n}f_{\lceil\frac{i}{j}\rceil}}{n-1}\)。提出\(\frac{n-1}{n......
  • 子树合并背包类型的 dp 的复杂度证明
    首先,我们发现,转移一颗子树的背包,实际上就是把该子树的根节点的所有儿子的子树背包合并,再与根节点合并。具体的,合并两颗子树的转移方程式如下:\[f(u,i)=\max\limits_{j+k=i}\{f(v_1,j)+f(v_2,k)\}\]于是有如下伪代码:dfs(u): su=1 f(u,1)=w[u] for(vinu) sv=siz......
  • 关于一类期望 dp 的公式推导
    想写但想不起来写啥......
  • 实现文档AI搜索,提高问题解决效率
    在当今的数字时代,以AI为动力的文档搜索变得越来越重要。随着在线提供信息的指数增长,传统的搜索方法通常效率低下且耗时。实施文档AI搜索可以显著提高搜索相关文档的效率和有效性。|在网站中实施文档AI搜索的好处很多首先,它通过提供无缝且直观的搜索过程来增强用户体验。借助文档AI......
  • 【基环树 | 题解】P5022 [NOIP2018 提高组] 旅行
    前言一日知基环树弱,固补题。关于基环树基环树定义一个环,环上每个点都有一颗以该点为根的树,如下图为一棵基环树关于基环树常规思路通常来说基环树常规思路是先处理环上树的结果,后通过树的结果来处理换上结果。具体处理方式依照题目来定。然而只是通常来说因为基环树的问......
  • Letter Picking (CF D) (区间DP, 暴力)(0,1,2 Alice 平 bob ,尽可能小,尽可能大)
     思路:区间dp(区间DP的时间复杂度不一定是n^3,可能是n^2更具题意)直接题直接区间dp,0Alice赢1平局2Bob赢(于是alice尽可能小,bob尽可能大)alice选l,bob可以选l+1,或者ralice选r,bob可选l或者r-1,看代码就行了#include<bits/stdc......