【BZOJ4300】绝世好题(二进制,DP)
2024-09-05 18:49:46
题意:
n<=100000,ai<=2*10^9
思路:按二进制逐位考虑,只要有至少1位取and后为1就可以接下去
设dp[i]为第i位取and之后为1的最长的序列长度,意会一下
#include<cstdio>
#include<iostream>
typedef long long ll;
using namespace std;
#define MOD 1000000007
#define N 110000
int a[N],dp[]; int main()
{
int n;
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%d",&a[i]);
for(int i=;i<=n;i++)
{
int tmp=;
for(int j=;j<=;j++)
if(a[i]&(<<(j-))) tmp=max(tmp,dp[j]);
tmp++;
for(int j=;j<=;j++)
if(a[i]&(<<(j-))) dp[j]=max(dp[j],tmp);
}
int ans=;
for(int i=;i<=;i++) ans=max(ans,dp[i]);
printf("%d\n",ans);
return ;
}
最新文章
- 搜索引擎系列 ---lucene简介 创建索引和搜索初步
- 用Redis打造URL缩短服务
- 在cmd下编译一个简单的servlet时出现程序包javax.servlet不存在
- linux常用命令:4文件压缩和解压命令
- 从零开始学ios开发(一):准备起航
- C++中cin、cin.get()、cin.getline()、getline()、gets()等函数的用法----细节决定成败 (sort用法)
- BZOJ_4326_[NOIP2015]_运输计划_(二分+LCA_树链剖分/Tarjan+差分)
- 补充一下sql server(临时表)
- 理解cookie的path和domain属性(转)
- 【转】 为什么我们做分布式使用Redis
- 在SOUI中使用线性布局
- Perl基础速成
- 程序的流程控制-分支结构 if
- pymysql 解决 sql 注入问题
- WPF版公司的自动签到程序
- freeswitch控制台日志级别设置以及存储
- 【RF库Collections测试】List Should Not Contain Duplicates
- Java Collections Framework概览
- ThinkPHP5 核心类 Request 远程代码漏洞分析
- R语言编程