51nod 1218 最长递增子序列 V2(dp + 思维)
2024-10-06 11:15:53
题目链接:https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1218
题解:先要确定这些点是不是属于最长递增序列然后再确定这些数在最长递增序列中出现的次数,如果大于1次显然是可能出现只出现1次肯定是必然出现。那么就是怎么判断是不是属于最长递增序列,这个只要顺着求一下最长递增标一下该点属于长度几然后再逆着求一下最长递减标一下该点属于长度几如果两个下标之和等于最长长度+1那么该点就属于最长递增序列,然后就是求1~len(len表示最长的长度)中各个长度出现的次数就行。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#define inf 0X3f3f3f3f
using namespace std;
const int M = 5e4 + 10;
int a[M] , b[M] , dpa[M] , dpb[M] , vis[M];
bool vs[M];
int binsearch(int l , int r , int num) {
int mid = (l + r) >> 1;
int ans = 0;
while(l <= r) {
mid = (l + r) >> 1;
if(b[mid] > num) r = mid - 1;
else {
ans = mid;
l = mid + 1;
}
}
return ans;
}
int binsearch2(int l , int r , int num) {
int mid = (l + r) >> 1;
int ans = 0;
while(l <= r) {
mid = (l + r) >> 1;
if(b[mid] < num) r = mid - 1;
else {
ans = mid;
l = mid + 1;
}
}
return ans;
}
int main() {
int n;
scanf("%d" , &n);
for(int i = 1 ; i <= n ; i++) scanf("%d" , &a[i]);
int len = 0;
b[0] = -1;
for(int i = 1 ; i <= n ; i++) {
if(a[i] > b[len]) {
len++;
b[len] = a[i];
dpa[i] = len;
continue;
}
else {
int pos = binsearch(1 , len , a[i]);
b[pos + 1] = min(b[pos + 1] , a[i]);
dpa[i] = pos + 1;
}
}
int len2 = 0;
memset(b , inf , sizeof(b));
for(int i = n ; i >= 1 ; i--) {
if(a[i] < b[len2]) {
len2++;
b[len2] = a[i];
dpb[i] = len2;
}
else {
int pos = binsearch2(1 , len2 , a[i]);
b[pos + 1] = max(b[pos + 1] , a[i]);
dpb[i] = pos + 1;
}
}
memset(vs , false , sizeof(vs));
for(int i = 1 ; i <= n ; i++) {
if(dpa[i] + dpb[i] == len + 1) {
vis[dpa[i]]++;
vs[i] = true;
}
}
printf("A:");
for(int i = 1 ; i <= n ; i++) {
if(vis[dpa[i]] > 1 && vs[i]) printf("%d " , i);
}
printf("\n");
printf("B:");
for(int i = 1 ; i <= n ; i++) {
if(vis[dpa[i]] == 1 && vs[i]) printf("%d " , i);
}
printf("\n");
return 0;
}
最新文章
- Django模型层Meta内部类详解
- 使用sklearn优雅地进行数据挖掘
- [Android Pro] proguard
- COJ986 WZJ的数据结构(负十四)
- Java异步IO/NIO
- ASP.Net MVC利用NPOI导入导出Excel
- javascript中false值及其常见比较运算
- CSU1312:榜单(模拟)
- 一份React-Native学习指南-感谢分享
- 原理图产生网络表后导进PADS之后,网络乱了的问题
- Android 关于资源适配
- 使用MySQL命令行新建用户并授予权限的方法
- SVGEditor
- Ubuntu 分辨率调整及操作问题解决
- 【NOI2004】郁闷的出纳员(splay)
- ubuntu14.04 网络配置
- C++回顾day02---<;引用>;---待补充
- 『Python』setup.py简介
- 在Linux系统中增加和删除用户
- postMessage和sendMessage