首页 > 其他分享 >单调队列优化DP解题报告(uoj转)

单调队列优化DP解题报告(uoj转)

时间：2024-09-27 09:01:23浏览次数：13  
标签：fr int max tt back 解题 uoj include DP

Fence

\(K\)很小，考虑\(K\)开一维，\(N\)开一维

\(f_{i,j}\)表示前\(i\)个工匠粉刷前\(j\)个木板的最大花费

\(f_{i,j}=\min_{k=j-l_i}^{s_i-1} f_{i-1,k}+(j-k) \cdot p_i\)

拆开为

\(f_{i,j}=f_{i-1,k}-k \cdot p_i+j \cdot p_i\)

\(i\)固定时维护\(f_{i-1,k}-k \cdot p_i\)的最小值即可

应该维护一个从\(s_i-1\)开始的后缀min，单调队列也行，但数组更香

PS:数据范围是不是错了，调了一年

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define fr(i,a,b) for(int i=a;i<=b;i++)
#define N 105
#define M 160005
#define ll long long
int n,m,L[N],P[N],S[N];
ll mn[M],f[N][M];
struct node{
	int l,p,s;
}a[N];
bool cmp(node A,node B){
	return A.s<B.s;
}
int main(){
	scanf("%d%d",&m,&n);
	fr(i,1,n)scanf("%d%d%d",&a[i].l,&a[i].p,&a[i].s);
	sort(a+1,a+n+1,cmp);
	fr(i,1,n)L[i]=a[i].l,P[i]=a[i].p,S[i]=a[i].s;
	fr(i,1,n){
		memset(mn,-0x3f,sizeof mn);
		for(int j=S[i]-1;j>=0;j--)mn[j]=max(mn[j+1],f[i-1][j]-1ll*j*P[i]);
		fr(j,S[i],S[i]+L[i]-1)f[i][j]=mn[max(0,j-L[i])]+1ll*j*P[i];
		fr(j,1,m)f[i][j]=max(f[i][j],max(f[i-1][j],f[i][j-1]));
	}
	printf("%lld\n",f[n][m]);
	return 0;
}

P2569 [SCOI2010]股票交易

其实不难，嘴巴AC算了

\(f_{i,j}\)表示第\(i\)天持有\(j\)股，当前收益max值

然后就是大分讨，拆式子，单调队列

#include<bits/stdc++.h>
using namespace std;
#define fr(i,a,b) for(int i=a;i<=b;i++)
#define N 2021
#define inf 0x3f3f3f3f
int n,m,k,ap[N],bp[N],as[N],bs[N],f[N][N];
deque<int> q;
int main(){
	scanf("%d%d%d",&n,&m,&k);
	fr(i,1,n)scanf("%d%d%d%d",&ap[i],&bp[i],&as[i],&bs[i]);
	memset(f,-0x3f,sizeof(f));
	fr(i,1,n){
		fr(j,0,as[i])f[i][j]=-j*ap[i];
		fr(j,0,m)f[i][j]=max(f[i][j],f[i-1][j]);
		if(i<=k)continue;
		q.clear();
		fr(j,0,m){
			while(q.size()&&j-q.front()>as[i])q.pop_front();
			while(q.size()&&f[i-k-1][j]+j*ap[i]>=f[i-k-1][q.back()]+q.back()*ap[i])q.pop_back();
			q.push_back(j);
			if(q.size())f[i][j]=max(f[i][j],f[i-k-1][q.front()]+(q.front()-j)*ap[i]);
		}
		q.clear();
		for(int j=m;j>=0;j--){
			while(q.size()&&q.front()-j>bs[i])q.pop_front();
			while(q.size()&&f[i-k-1][j]+j*bp[i]>=f[i-k-1][q.back()]+q.back()*bp[i])q.pop_back();
			q.push_back(j);
			if(q.size())f[i][j]=max(f[i][j],f[i-k-1][q.front()]+(q.front()-j)*bp[i]);
		}
	}
	printf("%d",f[n][0]);
	return 0;
}

P4954 [USACO09OPEN]Tower of Hay G

题目大意：\(n\)个数划分成若干个连续段，前一段sum\(\geq\)后一段sum，问最多划分几段

一个明显的DP是:
\(f_{i,j}\)表示前\(i\)个,最后一段为\(i\)~\(j\)的最高层数

但很遗憾这样最少也是\(n^2\)无法再优化了

考虑干掉第二维

手玩几组样例后发现，最优解一定是可行解中底部最小的

直觉上就是传上去了，不亏

证明用数归即可

因而只需确认底层最少几个，再递归即可

但还是难转移，因为底层看不到上面

所以只能从上面看下来

因此倒做

考虑\(f_i\)表示\(i\)~\(n\)分好的最高层数

\(g_i\)表示此时底层最小宽度

则\(f_i=\max_{j=i+1}^n f_j+1\) if \(s_{i...j-1} \geq g_j\)

\(O(n^2)\)

但是if后的条件\(s_{j-1}-s_{i-1} \geq g_j \leftrightarrow s_{i-1} \leq s_{j-1}-g_j\)

为了好看可改为后缀和

\(s_i-s_j \geq g_j\) , \(s_i \geq g_j+s_j\)

不难看出单调性，上优化即可

不得不说是个好题，值得一讲

#include<bits/stdc++.h>
using namespace std;
#define fr(i,a,b) for(int i=a;i<=b;i++)
#define N 100005
int n,a[N],s[N],f[N],g[N];
int q[N],hh,tt;
int main(){
	scanf("%d",&n);
	fr(i,1,n)scanf("%d",&a[n-i+1]);
	fr(i,1,n)s[i]=s[i-1]+a[i];
	fr(i,1,n){
		while(hh<=tt&&s[q[hh]]+g[q[hh]]<=s[i])hh++;
		g[i]=s[i]-s[q[hh-1]],f[i]=f[q[hh-1]]+1;
		while(hh<=tt&&s[q[tt]]+g[q[tt]]>=s[i]+g[i])tt--;
		q[++tt]=i;
	}
	printf("%d\n",f[n]);
	return 0;
}

P5665 [CSP-S2019] 划分

一模一样的题。。。

突然发现家里电脑没有int128？？？

空间实在恶心，88pts算了

#include<bits/stdc++.h>
using namespace std;
#define fr(i,a,b) for(int i=a;i<=b;i++)
#define N 40000005
#define ll long long
#define wow __int128
int n,typ,b1,b2,x,y,z,m,mod=(1<<30);
ll s[N],g[N];
wow f[N];
int q[N],hh,tt;
void write(wow x){
	if(x>(wow)9)write(x/10);
	putchar(x%10+'0');
}
int get(int i){
	if(i<=2)return i==1?b1:b2;
	else{
		int ans=(1ll*b2*x+1ll*b1*y+1ll*z)%mod;
		b1=b2,b2=ans;
		return ans;
	}
}
int main(){
	scanf("%d%d",&n,&typ);
	if(typ==0){
		fr(i,1,n){
			scanf("%d",&b1);
			s[i]=s[i-1]+b1;
		}
	}
	else{
		scanf("%d%d%d%d%d%d",&x,&y,&z,&b1,&b2,&m);
		int L=1,R,l,r;
		fr(i,1,m){
			scanf("%d%d%d",&R,&l,&r);
			fr(j,L,R)s[j]=s[j-1]+(get(j)%(r-l+1))+l;
			L=R+1;
		}
	}
	fr(i,1,n){
		while(hh<=tt&&s[q[hh]]+g[q[hh]]<=s[i])hh++;
		hh--;
		g[i]=s[i]-s[q[hh]],f[i]=f[q[hh]]+(wow)g[i]*g[i];
		while(hh<=tt&&s[q[tt]]+g[q[tt]]>=s[i]+g[i])tt--;
		q[++tt]=i;
	}
	write(f[n]);
	return 0;
}

哦，看到某位大神题解，对于压空间深受启发，AC code：

#include<bits/stdc++.h>
using namespace std;
#define fr(i,a,b) for(int i=a;i<=b;i++)
#define N 40000005
#define ll long long
#define wow __int128
int n,typ,b1,b2,x,y,z,m,mod=(1<<30);
ll s[N],g[N];
struct node{
	int id;
	wow f;
};
deque<node> q;
void write(wow x){
	if(x>(wow)9)write(x/10);
	putchar(x%10+'0');
}
int get(int i){
	if(i<=2)return i==1?b1:b2;
	else{
		int ans=(1ll*b2*x+1ll*b1*y+1ll*z)%mod;
		b1=b2,b2=ans;
		return ans;
	}
}
int main(){
	scanf("%d%d",&n,&typ);
	if(typ==0){
		fr(i,1,n){
			scanf("%d",&b1);
			s[i]=s[i-1]+b1;
		}
	}
	else{
		scanf("%d%d%d%d%d%d",&x,&y,&z,&b1,&b2,&m);
		int L=1,R,l,r;
		fr(i,1,m){
			scanf("%d%d%d",&R,&l,&r);
			fr(j,L,R)s[j]=s[j-1]+(get(j)%(r-l+1))+l;
			L=R+1;
		}
	}
	node hh,tt;
	q.push_back((node){0,0});
	fr(i,1,n){
		while(q.size()&&s[q.front().id]+g[q.front().id]<=s[i])hh=q.front(),q.pop_front();
		q.push_front(hh);
		tt.id=i;
		g[i]=s[i]-s[hh.id],tt.f=hh.f+(wow)g[i]*g[i];
		while(q.size()&&s[q.back().id]+g[q.back().id]>=s[i]+g[i])q.pop_back();
		q.push_back(tt);
//		puts("orz");
	}
	write(q.back().f);
	return 0;
}

acwing 299.裁剪序列

很有趣的一个题

首先还是无脑DP，设\(f_i\)表示\(1\)到\(i\)分段最小代价

则\(f_i = f_j + maxa(i\)~\(j)\)

st表维护最值，\(O(n^2)\)转移即可

考虑优化，发现一段区间在满足和限制且最大值不变的情况下，一定会尽量扩张

因此可以找出对于\(i\)向左，使最大值改变的所有位置，从左到右记为\(p_1,p_2,...p_k\)

不难看出其单调递减，单调队列即可

\(p_i\)贡献为\(f_{p_i}+p_{i+1}\)

拿个堆维护一下就行

当然还有和限制，特判即可

#include<bits/stdc++.h>
using namespace std;
#define fr(i,a,b) for(int i=a;i<=b;i++)
#define N 100005
#define ll long long
int n,a[N],vis[N];
ll m,f[N];
int q[N],hh,tt;
struct node{
	int fo,la;
	ll d;
	friend bool operator < (node A,node B){
		return A.d>B.d;
	}
};
priority_queue<node> p;
int main(){
	scanf("%d%lld",&n,&m);
	fr(i,1,n){
		scanf("%d",&a[i]);
		if(a[i]>m){
			puts("-1");
			return 0;
		}
	}
	ll sum=0;
	int j=0;
	fr(i,1,n){
		sum+=a[i];
		while(sum>m)sum-=a[++j];
		while(hh<=tt&&q[hh]<j)vis[q[hh++]]=1;
		while(hh<=tt&&a[i]>=a[q[tt]])vis[q[tt--]]=1;
		if(hh<=tt)p.push((node){q[tt],i,f[q[tt]]+a[i]});
		q[++tt]=i;
		f[i]=f[j]+a[q[hh]];
		p.push((node){q[tt],i,f[q[tt]]+a[i]});
		while(p.size()&&(vis[p.top().fo]||vis[p.top().la]))p.pop();
		if(p.size())f[i]=min(f[i],p.top().d);
	}
	printf("%lld\n",f[n]);
	return 0;
}

总结：状态尽量设计的好看一些，分离各个变量，就能用单调队列了

标签：fr,int,max,tt,back,解题,uoj,include,DP
From： https://www.cnblogs.com/zsj6315/p/18434961

相关文章

  • log型数据结构优化DP解题报告(uoj)
    交作业用T220417最长公共上升子序列不难看出状态同最长公共子序列，但由于上升条件限制，加一个限制：\(f_{i,j}\)表示\(a_{1...i}\)匹配\(b_{1...j}\)且\(a_i\)必须做结尾的最长公共上升子序列长度转移方程为\(f_{i,j}=f_{i,j-1}\)(if\(a_i\neqb_j\))\(f_{i,j}=\max_{k......
  • CF套题4翻译（uoj转载）
    \(A\)题：CF1098A给你一棵树，树根为\(1\)号点。每个点\(i\)有一个非负整数权值\(a_i\)，记点\(i\)到根的路径上经过的所有点（包括根和自身）的权值总和为\(s_i\)。现在擦去所有深度为偶数的点的\(s_i\)，求\(\suma_i\)最小可能是多少，如果无解，输出\(-1\)。被擦去的\(s_i\)在输入文件中被......
  • 我的 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阅读须知        技术文章仅供参考，此文所提供的信息只为网络安全人员对自己所负责的网站、服务器等（包括但不限于）进行检测或维护参考，未经授权请勿利用文章中的技术资料对任何计算机系统进行入侵操作。利用此文所提供的信息而造成的直接或间接后果和损失，均由使用......
  • 使用nc命令检测UDP端口
    使用nc命令检测UDP端口也是非常的简单，需要注意的是，所安装nc的版本不同，使用选项有点差异。1、检测开启的UDPnc-vuz192.168.2.2015353nc-vuz192.168.2.20137430端口正常启用时，会提示“UDPpacketsentsuccessfully”2、检测未开启的UDPnc-vuz192.168.2.2015354n......
  • 子集反演 & sos dp 学习笔记
    子集反演&sosdp学习笔记子集反演设\(g(S)\)表示集合\(S\)的答案，\(f(S)\)为\(S\)的子集的答案和。根据定义：\[f(S)=\sum_{T\inS}g(T)\]子集反演就是：\[g(S)=\sum_{T\inS}(-1)^{|S|-|T|}f(T)\]本质上就是容斥原理，可感性理解，证明略（给你你也记不住）。于是便可以通......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99