首页 星云 工具 资源 星选 资讯 热门工具
:

PDF转图片 完全免费 小红书视频下载 无水印 抖音视频下载 无水印 数字星空

P6764 [APIO2020] 粉刷墙壁

编程知识
2024年08月03日 10:23

思路:

本质上能进行的操作就是我们算出从第 \(i\) 块砖开始,连续刷 \(M\) 块砖,是否有承包商可以刷出期望颜色。

那么设 \(f_i\) 表示 \([i,i+m-1]\) 是否合法,那么就变成了最小区间覆盖问题。

最小区间覆盖问题

\(Max\) 表示当前覆盖了 \([1,Max]\)

那么我们需要找到左端点在 \([1,Max+1]\) 内,且右端点最大的区间。

在本题中因为区间长度都为 \(m\),那么我们只需要找到尽可能在最后的合法 \(f_i\)

此时 \(Max \gets i+m-1\),那么对于小于 \(j\)\(i\),是无法覆盖到 \(i+m-1\) 之后的,于是就没有贡献了,于是我们可以直接走指针维护。

最小区间覆盖代码
ll get(){
	ll Max=-1,x=0,id,ans=0;
	while(Max<n-1){
		id=-1;
		while(x<=Max+1&&x<n){
			if(f[x])
			  id=x;
			x++;
		}
		if(id==-1)
		  return -1;
		Max=id+m-1;
		ans++;
	}
	return ans;
}

那么我们需要考虑的就是如何求出 \(f_i\)

28pts:

对于每个 \(i\),暴力枚举一个 \(j\),然后查看是否能匹配上。

时间复杂度为 \(O(NM^2)\)

51pts:

考虑动态规划优化,定义 \(dp_{i,j}\) 表示从第 \(i\) 块墙壁开始,从第 \(j\) 个商家开刷最多能刷几块墙。

那么若第 \(j\) 个商家不能刷第 \(i\) 个墙壁,则:

\[dp_{i,j}=0 \]

否则能刷:

\[dp_{i,j} = dp_{i+1,(j+1) \bmod M} + 1 \]

注意,空间开不下,考虑滚动数组优化。

时间复杂度为 \(O(NM)\)

震惊的是,这玩意儿竟然过了……

离大谱。

$O(NM)$ 代码
int minimumInstructions(int N, int M, int K,vector<int> C,vector<int> A,vector<vector<int>> B){
	n=N,m=M,k=K;
	for(int i=0;i<n;i++)
	  a[i]=C[i];
	for(int i=0;i<m;i++){
		len[i]=A[i];
		for(auto v:B[i])
		  s[v].push_back(i);
	}
	for(int i=n-1;i>=0;i--){
		for(int j=0;j<m;j++)
		  dp[i&1ll][j]=0;
		for(auto j:s[a[i]]){
			dp[i&1ll][j]=dp[(i&1ll)^1ll][(j+1)%m]+1;
			if(dp[i&1ll][j]>=m)
			  f[i]=1;
		}
	}
	cerr<<'\n'<<abs(&Begin-&End)/1048576<<"MB"<<'\n';
	return get();
}

100pts:

注意到可以优化上面状态转移的 \(j\)

我们可以提前预处理能刷颜色 \(x\) 的承包商的集合 \(S_x\),那么 \(j \in S_{c_i}\)

但是因为是滚动数组,实时清空的话复杂度又上去了,那么再维护一个时间戳即可。

时间复杂度为 \(O(\sum f(k))\)

完整代码:

#include<bits/stdc++.h>
#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)
#define lowbit(x) x&(-x)
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define iip pair<pair<ll,ll>,ll>
#define ppii pair<pair<ll,ll>,pair<ll,ll>>
#define fi first
#define se second
#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x
#define Full(a) memset(a,0,sizeof(a))
#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);
using namespace std;
typedef double db;
typedef unsigned long long ull;
typedef int ll;
bool Begin;
const ll N=100100,M=50050;
inline ll read(){
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
          f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
inline void write(ll x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9)
	  write(x/10);
	putchar(x%10+'0');
}
ll n,m,k;
ll a[N],len[M];
ll dp[2][M],low[2][M];
vector<ll> s[N];
bool f[N];
bool End;
ll get(){
	ll Max=-1,x=0,id,ans=0;
	while(Max<n-1){
		id=-1;
		while(x<=Max+1&&x<n){
			if(f[x])
			  id=x;
			x++;
		}
		if(id==-1)
		  return -1;
		Max=id+m-1;
		ans++;
	}
	return ans;
}
int minimumInstructions(int N, int M, int K,vector<int> C,vector<int> A,vector<vector<int>> B){
	n=N,m=M,k=K;
	for(int i=0;i<n;i++)
	  a[i]=C[i];
	for(int i=0;i<m;i++){
		len[i]=A[i];
		for(auto v:B[i])
		  s[v].push_back(i);
	}
	for(int i=n-1;i>=0;i--){
		for(auto j:s[a[i]]){
			if(low[(i&1ll)^1ll][(j+1)%m]!=i+1)
			  dp[i&1ll][j]=1;
			else
			  dp[i&1ll][j]=dp[(i&1ll)^1ll][(j+1)%m]+1;
			low[i&1ll][j]=i;
			if(dp[i&1ll][j]>=m)
			  f[i]=1;
		}
	}
	cerr<<'\n'<<abs(&Begin-&End)/1048576<<"MB"<<'\n';
	return get();
}
From:https://www.cnblogs.com/rgw2010/p/18340226
本文地址: http://www.shuzixingkong.net/article/739
0评论
提交 加载更多评论
其他文章 python3解析wav文件获取dtmf值
操作系统 :Windows 10_x64 Python版本:3.9.2 从事FreeSwitch相关工作,大概率会遇得到DTMF,DTMF的传递方式有三种: In-band RFC2833 SIP-INFO 使用RFC2833或SIP-INFO传递方式的DTMF,FreeSwitch可以在日志中打印
python3解析wav文件获取dtmf值 python3解析wav文件获取dtmf值 python3解析wav文件获取dtmf值
技术资产建设
企业里的研发部门、技术团队其实更多的是软件/互联网公司的生产部门,好比实体产业的生产车间。生产车间可以通过更新车床、设备来提高生产力,这里的车床、设备即是“资产”,那么研发部门的“资产”类比一下就出来了,就是部门级的技术标准、工具。 对于团队人效来说,统一的技术库、技术组件能够形成有效的技术隔离带,
技术资产建设 技术资产建设 技术资产建设
Python的GDAL库绘制多波段、长时序遥感影像时间曲线图
本文介绍基于Python中的gdal模块,对大量长时间序列的栅格遥感影像文件,绘制其每一个波段中、若干随机指定的像元的时间序列曲线图的方法~
Python的GDAL库绘制多波段、长时序遥感影像时间曲线图 Python的GDAL库绘制多波段、长时序遥感影像时间曲线图 Python的GDAL库绘制多波段、长时序遥感影像时间曲线图
TinyVue v3.17.0 正式发布,推出了一款基于 Quill 2.0 的富文本编辑器,功能强大、开箱即用!
你好,我是 Kagol。 我们非常高兴地宣布,2024年6月26日,TinyVue 发布了 v3.17.0 &#127881;。 TinyVue 每次大版本发布,都会给大家带来一些实用的新特性,上一个版本我们重构了 chart-core,新增 CircleProcessChart 圆环进度图等6个新
TinyVue v3.17.0 正式发布,推出了一款基于 Quill 2.0 的富文本编辑器,功能强大、开箱即用! TinyVue v3.17.0 正式发布,推出了一款基于 Quill 2.0 的富文本编辑器,功能强大、开箱即用! TinyVue v3.17.0 正式发布,推出了一款基于 Quill 2.0 的富文本编辑器,功能强大、开箱即用!
LogCat连接安卓手机拉取日志到本地(Unity开发版)
unity开发游戏的时候经常会碰到安卓手机真机报错/崩溃,定位问题需要拉取安卓手机上的日志到电脑上来查看。 1. unity安装的时候,勾选安卓模块(sdk这些记得勾选安装) 2. 打开对应安卓模块个目录下的adb目录, 当前我的安装目录为C:\Program Files\Unity\Hub\Edi
LogCat连接安卓手机拉取日志到本地(Unity开发版) LogCat连接安卓手机拉取日志到本地(Unity开发版) LogCat连接安卓手机拉取日志到本地(Unity开发版)
前端性能优化---防抖与节流--02
防抖(Debounce)和节流(Throttle)是两种常用的优化技术,主要用于控制高频率的事件触发,如滚动、输入、窗口调整大小等。本文将深入探讨防抖与节流的原理、实现方法及其应用场景。 简单场景就是:输入框防抖,滚动节流 1. 防抖(Debounce) 防抖是一种在事件频繁触发时,通过延迟执行来减
ComfyUI插件:ComfyUI layer style 节点(三)
前言: 学习ComfyUI是一场持久战,而ComfyUI layer style 是一组专为图片设计制作且集成了Photoshop功能的强大节点。该节点几乎将PhotoShop的全部功能迁移到ComfyUI,诸如提供仿照Adobe Photoshop的图层样式、提供调整颜色功能(亮度、饱和度、对比度
ComfyUI插件:ComfyUI layer style 节点(三) ComfyUI插件:ComfyUI layer style 节点(三) ComfyUI插件:ComfyUI layer style 节点(三)
参加阿里云X优酷AI江湖创作大赛,赠送博客园T恤
8月刚开始就接到一个阿里云的广告单子,也是 CPA(Cost Per Action) 方式,按有效参赛人数付费,KPI是完成500人参赛。参赛方式是基于阿里云函数计算服务部署的AI绘画平台创作图片作品,参赛者基于网剧《少年白马醉春风》的故事内容、人物角色、场景或以“少年江湖”为精神内核进行自由创作
参加阿里云X优酷AI江湖创作大赛,赠送博客园T恤 参加阿里云X优酷AI江湖创作大赛,赠送博客园T恤 参加阿里云X优酷AI江湖创作大赛,赠送博客园T恤