热身训练2 The All-purpose Zero
2024-09-08 02:30:50
简要题意:
长度为n的数组,每个数字为S[i],$0$是一种很神奇的数字,你想要的,它都可以变!
问这个序列的最长上升子序列长度为多少?
分析:
我们将除了‘0’以外的S[i],减去i之前出现的‘0’的个数,最后求得排除‘0’后的最长上升子序列长度,加上‘0’的个数,就是我们要求的答案。
在这里我不主要分析该做法的正确性,我们引入一个O(nlogn)的方法来求最长上升子序列。
LIS (点此看题)
贪心+二分
我们令f[i]表示长度为i的上升子序列,末尾的最小值。
这里我们因为贪心,所以子序列末尾越小越好。
我们按顺序枚举给出的数组S[i],然后对f[]二分查找除小于S[i]的最大的f[j],并用它将f[j+1]更新。
#include<bits/stdc++.h>
using namespace std;
#define re register int
#define LL long long
const int N=1e5+5;
int n, a[N], b[N], len;
signed main()
{
scanf("%d",&n);
for(re i=1;i<=n;++i) scanf("%d",&a[i]);
for(re i=1;i<=n;++i)
{
if(a[i] > b[len]) b[++len] = a[i];
else
{
int tp = lower_bound(b+1, b+1+len, a[i])-b;
b[tp] = a[i];
}
}
printf("%d", len);
}
上马
#include<bits/stdc++.h>
using namespace std;
#define re register int
#define LL long long
const int N=1e5+5;
int n, a[N], b[N], num, len;
inline void work()
{
num = len = 0;
scanf("%d",&n);
for(re i=1;i<=n;++i)
{
scanf("%d",&a[i]);
if(a[i] == 0)
{
num ++;
a[i] = 1e9;
}
else
{
a[i] -= num;
}
}
b[0] = -1e9;
for(re i=1;i<=n;++i)
{
if(a[i] == 1e9) continue; if(a[i] > b[len]) b[++len] = a[i];
else
{
int tp = lower_bound(b+1, b+1+len, a[i])-b;
b[tp] = a[i];
}
}
printf("%d\n", len+num);
}
signed main()
{
int T;
scanf("%d",&T);
for(re i=1;i<=T;++i)
{
printf("Case #%d: ",i);
work();
}
return 0;
}
最新文章
- iOS NSNotificationCenter详解
- Google Map API V3开发(4)
- linux rpm安装apache php mysql
- ubuntu 14.04 java开发环境搭建 jdk 以及 inteliJ IDEA安装
- ubuntu共享文件配置
- flexbox简介
- sqlserver中常用的全局变量
- 解决iOS内存泄露
- 如何设置win7系统的文件夹为系统文件,从而隐藏文件夹
- Swift - 类型属性(类静态属性)和类方法(类静态方法)
- php 两个文件之间的相对路径的计算方法
- YUI 的模块信息配置优先级关系梳理
- PHP命名空间与自动加载类详解
- HttpClient post提交数据,返回json
- mac环境使用ATS验证
- phpcms配置列表页以及获得文章发布时间
- 转-JavaWeb三大组件之Listener监听器
- 金蝶k3密码批量修改
- C# 控件置于最顶层、最底层
- MySQL与Oracle之间互相拷贝数据的Java程序
热门文章
- 关于Golang的学习路线
- XML解析——Jsoup解析器
- File Upload(文件上传)
- CodeForce-808C Tea Party(结构体排序贪心)
- dede织梦会员模板调用template下模板head.htm方法及解析变量
- dede新增字段调用方法
- Java-Ide快速创建getter&;setter方法
- 关于selenium添加使用代理ip
- 完美解决JavaIO流报错 java.io.FileNotFoundException: F:\ (系统找不到指定的路径。)
- SpringBoot之SpringSecurity权限注解在方法上进行权限认证多种方式