Luogu-P3205-HNOI2010-合唱队
2024-09-07 03:15:36
题目地址
思路
这道题其实是P3146 [USACO16OPEN]248的升级版,但是N的范围很大,为262144。原先的O(N3)的方法自然会TLE,甚至O(N2)的方法也不足以解决。
定义f[i][j]为从左端点j开始,能合并出i的(右端点值+1)的值
首先进行初始化,对于坐标为i点的值t,处理如下:
他的左断点为i,能合并出的值为t,右端点为i,值赋予i+1
为什么是i+1呢?因为我们之后合并两个数的时候,从f[i][j]去搜,可以直接将其作为左端点搜索下一个数。
转移方程为:
\[f[i][j]=f[i-1][f[i-1][j]]
\]
\]
为什么?
\(f[i-1][j]\)代表从端点j开始找能合并成i-1的最少距离,并找出右端点的下一个端点。
\(f[i-1][f[i-1][j]]\)就代表从上一个找到的右端点下个端点开始搜索。如果没有搜到,肯定返回时0,就说明没有找到。
所以,如果当\(f[i][j]\)不为0后,这个i就是最大合并的值。
所以我们只要枚举i与j就可以了。
j的范围是n,那i呢?
我们知道,数最大是40,两个40合成一个41,四个40合成一个42,八个40合成一个43,十六个40合成一个44。
假设数都是最大的40,可以得出2^x个数字可以合成最大的值为40+x。
又因为N=262144,而且2^18=262144,所以最大的合成数为40+18=58,我们只要枚举到58就行了。
代码示例
#include<cstdio>
using namespace std;
int f[61][262145],n,x,ans;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&x),f[x][i]=i+1;
for(int i=2;i<=58;i++){
for(int j=1;j<=n;j++){
if(!f[i][j])f[i][j]=f[i-1][f[i-1][j]];
if(f[i][j])ans=i;
}
}
printf("%d",ans);
return 0;
}
PS:当然,把数组开反也是可以的。
最新文章
- GDB调试32位汇编堆栈分析
- Python学习笔记(4):自定义时间类
- http://runjs.cn/
- 递归遍历树结构顺序显示并且添加到list集合
- android的activity的跳转
- Oracle Berkeley DB Java 版
- mac Word 怎样放大缩小文档结构图文字大小
- Floodlight controller 线程池模型
- 小程序开发过程中常见问题[微信小程序、支付宝小程序]
- 详解Linux下swig 3.0.12的手动安装过程
- Java HashMap工作原理及实现[转]
- tcpdf开发文档(中文翻译版)
- Win32汇编学习(11):对话框(2)
- 第16月第17天 contentMode
- 面向对象编程其实很简单——Python 面向对象(初级篇)
- 13.Mysql触发器
- 远端访问MySQL
- 21天实战caffe笔记_第二天
- 解决Oracle监听错误的一种办法
- 实验三 Java敏捷开发与XP实践
热门文章
- UNP——第二章,TCP状态,TIME_WAIT
- Innodb自增主键与sql_mode
- 预估ceph的迁移数据量
- Java编码和字符集(详解)
- [LeetCode题解]109. 有序链表转换二叉搜索树 | 快慢指针 + 递归
- Spring Cloud实战 | 最八篇:Spring Cloud +Spring Security OAuth2+ Axios前后端分离模式下无感刷新实现JWT续期
- Spark闭包 | driver &; executor程序代码执行
- 通过Tomcat Manager拿shell
- Jinja2语法自动补全配置
- 2020.10.17 JZOJ 提高B组T2 导弹拦截