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

P3147 [USACO16OPEN] 262144 P

\(f_{i,j}\) 表示从 \(i\) 开始凑出 \(j\) 的连续段的右端点的下一个位置, 初始 \(\forall i\in [1,n], f_{i,a_i}=i+1\), 转移 \(f_{i,j}=f_{f_{i,j-1},j-1}\),和倍增很像。

注意转移时不要让 \(j=a_i\) 否则 \(f_{i,a_i}\) 就变成 \(0\) 了,后面的转移就会出错。

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
typedef unsigned long long ll;
int n,a[N],f[N][60];
int main(){ios::sync_with_stdio(0),cin.tie(0);cin>>n;for(int i=1;i<=n;i++)cin>>a[i],f[i][a[i]]=i+1;int ans=0;for(int j=1;j<=58;j++){for(int i=1;i<=n;i++){if(a[i]!=j)f[i][j]=f[f[i][j-1]][j-1];if(f[i][j])ans=j;}}cout<<ans;return 0;
}
http://www.hskmm.com/?act=detail&tid=34888

相关文章:

  • 智能交付时代:国内企业如何选择最适合的CI/CD工具?
  • 吴恩达深度学习课程一:神经网络和深度学习 第三周:浅层神经网络(三)
  • 2025 年最新彩钢瓦厂家推荐排行榜:屋顶 / 防水 / 屋面等优质产品精选压型 /0.5 厚/屋面/墙面彩钢瓦公司推荐
  • 结对项目--实现一个自动生成小学四则运算题目的命令行程序
  • LCA
  • 【测试分类 (下)】测试分类看这篇就够了:彻底告别概念混淆,轻松搞定工作面试 - 指南
  • 树状数组
  • 如何管控文件外发安全,确保企业数据不被泄露
  • 打通CI/CD最后一公里:制品库如何成为高效流水线的核心枢纽
  • 2025年10月高端奢侈家电品牌推荐排行榜及深度对比分析
  • 嵌入式调式方案:
  • 2025年10月高端奢侈家电品牌推荐排行榜对比与深度评测分析
  • 2025年GEO品牌推荐排行榜前十强权威发布
  • 2025年GEO品牌推荐榜与排行榜Top10:权威解析与行业洞察
  • 2025年10月高端奢侈家电品牌推荐排行榜单对比与评测分析
  • 第五章 linux实战-CMS01
  • 字典树
  • 2025年10月高端奢侈家电品牌推荐排行榜:五大品牌综合对比与选购指南
  • mysql 更新默认时间
  • A. Vasya and Petyas Game
  • Android Studio Archive | Android Studio 归档下载
  • 关系型数据库的基本理论
  • JAVA集合
  • 【最新推荐】分享十大常用又靠谱的文件摆渡系统
  • C语言实现LDPC码译码功能
  • 2025年10月中国试验机厂家推荐:十强榜单对比与性能评测
  • [NOIP 2012 提高组] 开车旅行 的AC代码
  • Voice Chat: Resolving Lag and Stuttering with a Jitter Buffer
  • 2025 年报警器经销商最新推荐榜单:全面剖析海湾、青鸟等品牌服务商优势,为您筛选优质可靠合作伙伴燃气 / 太阳能 / 交通道路报警器推荐
  • 结构体