codeforces 486 E. LIS of Sequence（dp）
2024-09-01 04:57:35
题目链接：http://codeforces.com/contest/486/problem/E
题意：给出n个数，如果一个数满足不属于最长递增序列，那么输出1，如果属于最长递增序列但是不属于所有最长递增序列的输出2。
如果属于所有最长递增序列的输出3。
题解：这里要用点技巧，不妨设dpBefore[i]表示以第i位为结尾的最长递增序列长，dpAfter[i]表示以第i位为结尾的最长递增序列长。
然后只要满足dpBefore[i]+dpAfter[i]=len（len表示最长递增序列为多长用二分的lis求的），至于这个点是属于所有的递增序列还
是不是，只要存在j使得dpAfter[i]=dpAfter[j]，那么就是不属于所有的最长递增序列。
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int M = 1e5 + 10;
int a[M] , b[M] , a2[M] , b2[M] , dpBefore[M] , dpAfter[M] , flag[M] , cmp[M];
int binsearch(int num , int sta , int end) {
int l = sta , r = end;
int mid = (l + r) >> 1;
while(l <= r) {
mid = (l + r) >> 1;
if(b[mid] < num) l = mid + 1;
else r = mid - 1;
}
return r;
}
int binsearch2(int num , int sta , int end) {
int l = sta , r = end;
int mid = (l + r) >> 1;
while(l <= r) {
mid = (l + r) >> 1;
if(b2[mid] <= num) l = mid + 1;
else r = mid - 1;
}
return l;
}
int main() {
int n;
scanf("%d" , &n);
memset(cmp , 0 , sizeof(cmp));
for(int i = 1 ; i <= n ; i++) {
scanf("%d" , &a[i]);
a2[i] = a[i];
flag[i] = 0;
}
int len = 1;
b[len] = a[1];
for(int i = 2 ; i <= n ; i++) {
if(a[i] > b[len]) {
b[++len] = a[i];
dpBefore[i] = len - 1;
}
else {
int pos = binsearch(a[i] , 1 , len);
b[pos + 1] = a[i];
dpBefore[i] = pos;
}
}
int len2 = len;
b2[len2] = a[n];
for(int i = n - 1 ; i >= 1 ; i--) {
if(a[i] < b2[len2]) {
b2[--len2] = a[i];
dpAfter[i] = len - len2;
}
else {
int pos = binsearch2(a[i] , len2 , len);
b2[pos - 1] = a[i];
dpAfter[i] = len - pos + 1;
}
} for(int i = 1 ; i <= n ; i++) {
if(dpBefore[i] + dpAfter[i] == len - 1) {
flag[i] = 1;
cmp[dpAfter[i]]++;
}
}
for(int i = 1 ; i <= n ; i++) {
if(flag[i]) {
if(cmp[dpAfter[i]] > 1) {
printf("2");
}
else {
printf("3");
}
}
else {
printf("1");
}
}
printf("\n");
return 0;
}
最新文章
- JQuery EasyUI DataGrid根据条件设置表格行样式(背景色)
- Access数据库的模糊查询到底是用*还是%
- js-JavaScript高级程序设计学习笔记15
- AngularJS 国际化——Angular-translate
- 什么是multipart/form-data请求
- ThinkPHP去除url中的index.php
- Groupon面经：Find paths in a binary tree summing to a target value
- php中遍历二维数组并以表格的形式输出
- OC4_遵守多个协议
- php 处理高并发的思路
- python 调用shell或windows命令
- ios多线程操作（五）—— GCD串行队列与并发队列
- C#边边角角（一）
- FreeMarker 语法
- Activity竟然有两个onCreate方法，可别用错了
- 201521123020《java程序设计》 第11周学习总结
- box-shadow + animation 实现loading
- springboot+mybatis-puls利用swagger构建api文档
- Nginx编译安装：
- 关于git 命令的一些事