当前位置: 首页 > news >正文

luogu P8816 [CSP-J 2022] 上升点列 题解

luogu P8816 [CSP-J 2022] 上升点列 题解

tip:如果没有看过题,建议先点击标题中的链接看一眼题

题意简述

题目大意相信大家都能看懂(摸鱼),看懂了直接跳到思路部分即可。

如果你没有看懂题意,有下面两个题意选择:

注:以下是折叠框,请通过左边的小三角展开

1. 啰嗦而鬼畜版

这道题的题意实际上非常的简单易懂。就是在一个平面直角坐标系(如果你连这个都不知道就自行度娘)中,题中会给出神秘的互不相同 n 个整点(横纵坐标都为整数的点),此外可能是因为你获得了★全★新★的★力★量★,所以你可以自由添加 k 个整点。然后,我们把一个「好序列」定义为一个序列中每一个点的横纵坐标单调不减,即x_i=x_{i-1}+1或y_i=y_{i-1}+1,求你使用神秘的力量添加 k 个点之后能在这 n+k 个点中找出的最长的序列的长度

2. 极速版 题意十分简单。题中会给出 n 个不同的在一个平面直角坐标系中的整点,并且给出你可以添加的整点数 k ,要求求出一个最长的序列的长度,其中所有的点横纵坐标单调不减,即满足x_i=x_{i-1}+1或y_i=y_{i-1}+1。

思路

本题的思路也十分的简单哈,本人想了5min不到就出了(实际上写的时候还是出锅了)。

「显而易见」

显而易见,这道题求的是最长序列的长度,这是最优化问题,所以很容易想到 dp (如果不会 dp 的话出门右转oi-wiki搜动态规划即可),其次,结合题目名称“上升点列”,也不难看出,这道题的思路和LIS(最长上升子序列,不会出门右转……)有点相似。

「圆规正转」

我们言归正传,该讲这道题的具体思路了:
上 dp 四部曲!

  1. 状态:$dp_{i,j}$表示考虑前$i$个点,还剩$j$个可增加的点时的满足条件的最长点列长度(只考虑到以给出的某个整点,而非自己添加的整点为结尾)
  2. 答案:$max(dp_{i,j(1\le i\le n,0\le j\le k)}+j)$为什么要$+j$呢?因为现在还剩下$j$个点可以添加,所以肯定可以将它们全部加上来增加点列的长度
  3. 初值:$dp_{i,k(1\le i\le n)}=0$
  4. 转移:
曼哈顿前缀和数组的定义(建议看)

为了更为方便地求出任意两个点之间的曼哈顿距离(待会有用),我们要通过一个前缀和数组来优化区间求和(显然的) 以下是详细数组的定义: 如果我们将点 i 和 i-1 之间的曼哈顿距离记为 mht_i ,并将 mht 数组做一个前缀和,就会发现点 i 和 j (i>j)之间的曼哈顿距离为mht_i-mht_j。

如果不想看推出式子的过程的长篇大论,直接通过标签往下看即可。
>既然我换行了,说明转移稍微有一些难想。首先想到LIS是对于每一个点$i$,枚举它在序列中的上一个点$j$,然后由$j$推过来即可。所以不难想到这一道题也是如此。
>那么在预处理的时候先对这些点从低到高进行排序,$x$为第一关键字,$y$为第二关键字,这样可以使这些点稍微有一点顺序,但是还是需要特判$x$和$y$不符合条件的情况。
>这样的话,LIS中的那个“>”号的作用好像就被我们实现了啊?
>但是我们还得考虑一件十分重要的事情,那就是可以添加的那些点怎么处理。也就是说,我们如何计算从$j$到$i$需要的费用?(也就是需要添加多少个点?)
>我们不妨思考一下:首先,对于两个“相邻”的点i和j,即可以直接加入同一个序列的点,定义是这样的:满足$x_i=x_{j}+1$或$y_i=y_{j}+1$(这是题面中有说的,只不过小小的修改了一下)那我们就可以想到,两个整点的欧几里得距离为1其实跟它们两个的曼哈顿距离为1是没有区别的,而两个并不相邻的点想要构成递推的关系,要想办法将这两个点通过一些两两之间曼哈顿距离为1的点“连接”起来。
>那么要想让两个不相邻的整点$i$和$j$($i>j$)构成递推关系,需要增加$mht_i-mht_j-1$,也就是两点之间的曼哈顿距离-1个整点。
图解:
图解

最终的状态转移方程

dp[i][q]=max(dp[i][q],dp[j][q+dis]+dis+1);

AC Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=505,K=105;
int n,k;
struct points{int x,y;
}pts[N];//存点
int mht[N];//曼哈顿前缀和
int dp[N][K];//dp数组bool cmp(points a,points b){if(a.x==b.x){return a.y<b.y;}return a.x<b.x;
}//compare函数,注意关键字signed main(){cin>>n>>k;for(int i=1;i<=n;i++){cin>>pts[i].x>>pts[i].y;}sort(pts+1,pts+n+1,cmp);//排序for(int i=1;i<=n;i++){mht[i]=(pts[i].x-pts[i-1].x)+(pts[i].y-pts[i-1].y);mht[i]+=mht[i-1];}//预处理曼哈顿距离for(int i=1;i<=n;i++){dp[i][k]=1;//dp初值for(int q=0;q<=k;q++){for(int j=1;j<i;j++){if(pts[j].x>pts[i].x||pts[j].y>pts[i].y)continue;//特判不符合条件int dis=mht[i]-mht[j]-1;if(q+dis>k){continue;}//如果距离太远,转移不过来了就炸飞()dp[i][q]=max(dp[i][q],dp[j][q+dis]+dis+1);//转移}}}int ans=-1;for(int i=1;i<=n;i++){for(int j=0;j<=k;j++){ans=max(ans,dp[i][j]+j);//别忘了有+j}}//求最大值cout<<ans;//输出return 0;//华丽结束
}

The end

今天成功贡献了一个猎奇的题解!鄙人写的题解不是很好,望包涵。

http://www.hskmm.com/?act=detail&tid=25138

相关文章:

  • CF558C Amr and Chemistry BFS解
  • Atbash密码和摩斯密码
  • Redis 中如何保证缓存与数据库的内容一致性?
  • Payload CMS:开发者优先的Next.js原生开源解决优秀的方案,重新定义无头内容管理
  • 第一次写博客
  • 07. 自定义组件
  • python语法记录
  • 2025 年储罐厂家推荐最新公司权威排行榜榜单发布,深度解析衬四氟储罐 / 硫酸储罐 / 盐酸储罐工厂选购指南
  • UnicodeEncodeError: locale codec cant encode character \u5e74 in position 2: encoding error
  • 2025 年生物除臭设备厂家最新推荐排行榜:覆盖污水处理厂 / 垃圾中转站等多场景,助力企业精准挑选优质设备
  • 2025 年球墨铸铁管公司:重庆南恩物资全品类管材供应与市政工程适配解决方案解析
  • 2025生物除臭设备厂家最新品牌企业推荐排行榜揭晓:印染厂污水,食品厂污水,污水处理厂,污水泵站,污水站,餐厨垃圾,屠宰场,厨余垃圾生物除臭设备公司推荐
  • 2025 工业加热器选型必看:六大加热器实力厂家深度推荐,覆盖多场景加热设备解决方案
  • YOLO模型部署
  • 从理念到沙盘:用悟空博弈模拟器点亮人机共治的曙光
  • 深入解析:Redis事务详解:原理、使用与注意事项
  • phone num
  • Perplexity发布搜索API,驱动下一代AI应用开发
  • PWN手的成长之路-09-SWPUCTF 2023 秋季新生赛Shellcode
  • 20251005 总结
  • OKR1
  • 2025 年装盒机制造厂 TOP 企业品牌推荐排行榜,自动化 / 喷胶 / 牙膏 / 手机壳 / 3C 数码 / 内外盒 / 面膜 / 电子产品 / 玩具 / 日用品装盒机推荐这十家公司!
  • 英语_阅读_Chinas Spring Festival_待读
  • 2025 年自动包装生产线 TOP 企业品牌推荐排行榜!食品行业 / 日化产品 / 智能化 / 小型 / 多功能集成 / 柔性 / 后道 / 高速自动包装生产线推荐!
  • 题解:AT_arc181_e [ARC181E] Min and Max at the edge
  • 酵母单杂交实验:解密 “转录因子 - DNA 互作” 的核心工具
  • api调用钉钉群机器人发信息 - 规格严格
  • 2025 年氢氧化铝生产厂家 TOP 品牌榜单来袭,阻燃,高白,酸融,导热,超细,微粉级,低粘度,灌封胶用,覆铜板用氢氧化铝公司推荐!
  • 飞算 JavaAI 赋能老工程重构:破旧立新的高效利器
  • P14139 题解