首页 > 其他分享 >log型数据结构优化DP解题报告(uoj)

log型数据结构优化DP解题报告(uoj)

时间:2024-09-27 09:00:45浏览次数:7  
标签:fr log int mid using uoj include DP define

交作业用


T220417 最长公共上升子序列

不难看出状态同最长公共子序列,但由于上升条件限制,加一个限制:

\(f_{i,j}\)表示\(a_{1...i}\)匹配\(b_{1...j}\)且\(a_i\)必须做结尾的最长公共上升子序列长度

转移方程为

\(f_{i,j} = f_{i,j-1}\) (if \(a_i \neq b_j\))

\(f_{i,j} = \max_{k=1}^{i-1}{f_{k,j-1}+1}\) (且\(a_k \le a_i\)) (if \(a_i = b_j\))

时间复杂度\(O(n^3)\)

但由于\(j\)很少变动的良好性质,可先枚举\(j\)再枚举\(i\),并将\(a_k \le a_i\)条件改为\(a_k \le b_j\),因为\(a_i = b_j\)

开个变量记录当前max即可

时间复杂度\(O(n^2)\)


#include<bits/stdc++.h>
using namespace std;
#define fr(i,a,b) for(int i=a;i<=b;i++)
#define N 2022
int T,n,m,a[N],b[N],f[N][N]; 
int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		fr(i,1,n)scanf("%d",&a[i]);
		scanf("%d",&m);
		fr(i,1,m)scanf("%d",&b[i]);
		fr(i,1,n)f[1][i]=a[i]==b[1];
		fr(i,2,m){
			int mx=0;
			fr(j,1,n){
				f[i][j]=(b[i]==a[j]?max(mx+1,f[i-1][j]):f[i-1][j]);
				if(a[j]<=b[i])mx=max(mx,f[i-1][j]);
			}
		}
		int mx=0;
		fr(i,1,n)mx=max(mx,f[m][i]);
		printf("%d\n",mx);
	}
	return 0;
}


AcWing 297. 赤壁之战

按套路,\(N\)开一维,\(M\)开一维,仍考虑通过强制钦定来维护递增性质

\(f_{i,j}\)表示\(a_{1...i}\)中以\(a_i\)为结尾长度为\(j\)的严格递增子序列有几个

则\(f_{i,j}=\sum_{k=1}^{i-1}f_{k,j-1}\) (且\(a_k < a_i\))

仍然\(j\)少变,考虑先\(j\)后\(i\),拿树状数组维护前缀和即可

#include<bits/stdc++.h>
using namespace std;
#define fr(i,a,b) for(int i=a;i<=b;i++)
#define N 1005
#define mod 1000000007
int cases,n,m,a[N],te[N],cnt,f[N][N],t[N];
void discrete(){
	fr(i,1,n)te[i]=a[i];
	sort(te+1,te+n+1);
	cnt=unique(te+1,te+n+1)-(te+1); 
}
int qu(int x){
	return lower_bound(te+1,te+cnt+1,x)-te;
}
int lb(int x){
	return x&(-x);
}
void add(int x,int y){
	for(;x<N;x+=lb(x))t[x]=(t[x]+y)%mod;
}
int ask(int x){
	int res=0;
	for(;x;x-=lb(x))res=(res+t[x])%mod;
	return res;
}
int main(){
	scanf("%d",&cases);
	fr(css,1,cases){
		scanf("%d%d",&n,&m);
		fr(i,1,n)scanf("%d",&a[i]);
		discrete();
		fr(i,1,n)a[i]=qu(a[i]);
		fr(i,1,n)f[1][i]=1;
		fr(i,2,m){
			memset(t,0,sizeof t); 
			fr(j,1,n){
				f[i][j]=ask(a[j]-1);
				add(a[j],f[i-1][j]);
			}
		}
		int ans=0;
		fr(i,1,n)ans=(ans+f[m][i])%mod;
		printf("Case #%d: %d\n",css,ans);
	}
	return 0;
}

Minimizing maximizer

最终目的是将最大值移到最右端,因而考虑中间状态

\(f_i\)表示将最大值移到\(i\)号位置需要的排序数

转移方程为

\(\forall i \in [1,m]\),
\(f_{r_i}=\min\{f_{r_i},\min_{j = l_i}^{r_i}f_j+1\}\)

单点修改,区间求min,线段树即可

#include<iostream>
#include<cstdio>
using namespace std;
#define fr(i,a,b) for(int i=a;i<=b;i++)
#define N 50005
#define M 500005
int n,m,L[M],R[M];
struct SGT{
	int l,r,d;
}t[N<<2];
void push_up(int nd){
	t[nd].d=min(t[nd<<1].d,t[nd<<1|1].d);
}
void build(int nd,int L,int R){
	t[nd].l=L,t[nd].r=R;
	if(L==R)t[nd].d=M;
	else{
		int mid=(L+R)>>1;
		build(nd<<1,L,mid);
		build(nd<<1|1,mid+1,R);
		push_up(nd);
	}
}
void update(int nd,int x,int y){
	if(t[nd].l==t[nd].r)t[nd].d=min(t[nd].d,y);
	else{
		int mid=t[nd<<1].r;
		if(x<=mid)update(nd<<1,x,y);
		else update(nd<<1|1,x,y);
		push_up(nd);
	}
}
int ask(int nd,int L,int R){
	if(t[nd].l>=L&&t[nd].r<=R)return t[nd].d;
	else{
		int mid=t[nd<<1].r,res=M;
		if(L<=mid)res=min(res,ask(nd<<1,L,R));
		if(R>mid)res=min(res,ask(nd<<1|1,L,R));
		return res;
	}
}
int main(){
	scanf("%d%d",&n,&m);
	fr(i,1,m)scanf("%d%d",&L[i],&R[i]);
	build(1,1,n);
	update(1,1,0);
	fr(i,1,m)update(1,R[i],ask(1,L[i],R[i])+1);
	printf("%d\n",ask(1,n,n));
	return 0;
}

Best Cow Fences(nowcoder)

Best Cow Fences

题意不明。。。

实际上就是求长度\(\geq F\)的平均值最大的区间

平均值最大,直接上二分

设\(b_i = a_i - mid\),\(s_i = \sum_{j=1}^i b_j\)

找到\(i \leq j-F\)且\(s_i<=s_j\)即可

随便什么东西维护一下

好像不需要DP

好像很卡精度

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
#define fr(i,a,b) for(int i=a;i<=b;i++)
#define N 100005
const double eps = 1e-8;
int n,m,a[N];
double b[N];
int cmp(double x,double y){
	if(abs(x-y)<eps)return 0;
	if(x<y)return -1;
	return 1;
}
bool ch(double mid){
	fr(i,1,n)b[i]=b[i-1]+1.0*a[i]-mid;
	double mn=1e10;
	fr(i,m,n){
		mn=min(mn,b[i-m]);
		if(cmp(b[i],mn)>=0)return 1;
	}
	return 0;
}
int main(){
	scanf("%d%d",&n,&m);
	fr(i,1,n)scanf("%d",&a[i]);
	double l=0,r=2000,mid;
	while(abs(r-l)>1e-7){
		mid=(l+r)/2;
		if(ch(mid))l=mid;
		else r=mid;
	}
	printf("%d",int((l+0.00001)*1000));
	return 0;
}

Cleaning Shifts

不难看出可以按左端点排序,贪心选

具体而言,从左到右扫一遍,对于每个没被覆盖的点,选一个能盖到它的线段中右端点最右的就行

一看就是堆

《DP》

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
#define fr(i,a,b) for(int i=a;i<=b;i++)
#define N 25005
int n,m;
struct node{
	int l,r;
	friend bool operator < (node A,node B){
		return A.r<B.r;
	}
}a[N];
priority_queue<node> q;
bool cmp(node A,node B){
	return A.l<B.l;
}
int main(){
	scanf("%d%d",&n,&m);
	fr(i,1,n)scanf("%d%d",&a[i].l,&a[i].r);
	sort(a+1,a+n+1,cmp);
	int nowT=1,now=1,ans=0;
	while(nowT<=m){
		while(now<=n&&a[now].l<=nowT)q.push(a[now++]);
		if(q.empty()||q.top().r<nowT){
			puts("-1");
			return 0;
		}
		else{
			ans++;
			nowT=q.top().r+1;
			q.pop();
		}
	}
	printf("%d\n",ans);
	return 0;
}

总结:优化其实有迹可循,大多从维度、转移的特点入手,难点还是状态设计

log型常用数据结构:线段树、树状数组、平衡树等

其实DP与贪心也是有相似之处的

标签:fr,log,int,mid,using,uoj,include,DP,define
From: https://www.cnblogs.com/zsj6315/p/18434967

相关文章

  • 《HelloGitHub》第 102 期
    兴趣是最好的老师,HelloGitHub让你对编程感兴趣!简介HelloGitHub分享GitHub上有趣、入门级的开源项目。github.com/521xueweihan/HelloGitHub这里有实战项目、入门教程、黑科技、开源书籍、大厂开源项目等,涵盖多种编程语言Python、Java、Go、C/C++、Swift...让你在短......
  • CF套题4翻译(uoj转载)
    \(A\)题:CF1098A给你一棵树,树根为\(1\)号点。每个点\(i\)有一个非负整数权值\(a_i\),记点\(i\)到根的路径上经过的所有点(包括根和自身)的权值总和为\(s_i\)。现在擦去所有深度为偶数的点的\(s_i\),求\(\suma_i\)最小可能是多少,如果无解,输出\(-1\)。被擦去的\(s_i\)在输入文件中被......
  • go logrus输出json日志并转储
    相比于klog,logrus支持输出json日志,但是默认time不在最前面,而在最后,因为日志输出时按照key字母顺序排序。gogetgithub.com/sirupsen/logrusgogetgithub.com/natefinch/lumberjackpackagemainimport( "fmt" "io" "os" "path/filepath" "runtime"......
  • 我的 WordPress 网站上的 WP API 集成问题 – 寻求建议
    开发社区您好,我一直致力于通过集成多个API来增强我的WordPress网站WPTroubles.com的功能,但我遇到了一些问题,希望得到一些建议:RESTAPI端点响应不一致:我正在使用WPRESTAPI提取某些动态内容的数据,但我注意到某些端点响应不一致。有时它们会返回预期的数据,而有时它们会超......
  • 宝塔面板WordPress建站教程:海外服务器选择与详细安装步骤
     一、什么是宝塔面板?宝塔面板(BTPanel)是一款简单易用的服务器管理工具,适合那些不熟悉命令行操作的用户。它允许你通过一个图形化界面轻松管理服务器和网站,尤其适合新手用户快速搭建像WordPress这样的网站。二、准备工作选择服务器与域名搭建网站的第一步是选择合适的服务器......
  • USB2.0 DP DM VBUS
    在USB2.0中,设备成功枚举的标志可以通过观察D+(dp)、D-(dm)和VBUS引脚的电压波形来判断。以下是这些信号在USB2.0枚举过程中常见的状态:VBUS(5V供电):USB设备插入主机时,VBUS引脚应从0V变为5V。这表明主机为设备提供了电源,设备开始上电。D+和D-信号线状态:空闲状态......
  • 【项目实战】生命体征监测芯片ADPD7000调试
    概要ADPD7000作为多模式生命体征监测传感器前端,可以做到心率、心电、血氧、体脂等生命体征进行实时监测。极小的封装及强悍的功能用在小小的手表手环上,就可以测量出人体的多项数据。以下技术实现过程,具体一定驱动基础的伙伴能秒懂。技术细节硬件原理:驱动配置:以上P4_......
  • NOIP2024集训Day39 DP
    NOIP2024集训Day39DPA.[AGC002F]LeftmostBall反向考虑,从最终状态,倒退它能指向多少种初始状态。dp策略:从左往右放,每次对最左边的一个空位,要么放一个白球,要么放一个有颜色的球,同时把该种颜色剩下的球都放到后面的位置去。具体的:定义\(f_{i,j}\)表示当前有\(i\)个白球......
  • WordPress LearnPress插件 SQL注入漏洞
     0x01阅读须知        技术文章仅供参考,此文所提供的信息只为网络安全人员对自己所负责的网站、服务器等(包括但不限于)进行检测或维护参考,未经授权请勿利用文章中的技术资料对任何计算机系统进行入侵操作。利用此文所提供的信息而造成的直接或间接后果和损失,均由使用......
  • Python日志管理之Loguru
    1.安装pipinstallloguru2.快速使用fromloguruimportloggerlogger.add("my_log.log",rotation="10MB")#自动分割日志文件logger.info("这是一个信息级别的日志")3.日志器配置方式1.导入即用fromloguruimportlogger,有且只有1个日志器对象,简化配置复杂性2.日志器配......