51nod 1218 最长递增子序列 | 思维题

51nod 1218 最长递增子序列

题面

给出一个序列,求哪些元素可能在某条最长上升子序列中,哪些元素一定在所有最长上升子序列中。

题解

YJY大嫂教导我们,如果以一个元素结尾的LIS长度 + 以它开头的LIS长度 - 1 = n,那么这个元素可能在LIS中。

那么什么时候它一定在呢?就是它在LIS中的位置“无可替代”的时候,即:设以它结尾的LIS长度为x,以任何其它元素(不可能在LIS中的元素除外)结尾的LIS长度均不为x。

然后就做出来了!

#include <cstdio>
#include <cstring>
#include <algorithm>
#define INF 0x3f3f3f3f
#define space putchar(' ')
#define enter putchar('\n')
using namespace std;
typedef long long ll;
template <class T>
bool read(T &x){
char c;
bool op = 0;
while(c = getchar(), c < '0' || c > '9')
if(c == '-') op = 1;
else if(c == EOF) return 0;
x = c - '0';
while(c = getchar(), c >= '0' && c <= '9')
x = x * 10 + c - '0';
if(op) x = -x;
return 1;
}
template <class T>
void write(T x){
if(x < 0) putchar('-'), x = -x;
if(x >= 10) write(x / 10);
putchar('0' + x % 10);
}
const int N = 50005;
int n, a[N], s[N], cnt, lis[N], lds[N], type[N], tot[N];
int main(){
read(n);
for(int i = 1; i <= n; i++)
read(a[i]);
for(int i = 1; i <= n; i++){
if(!cnt || a[i] > s[cnt]) s[++cnt] = a[i], lis[i] = cnt;
else {
int pos = lower_bound(s + 1, s + cnt + 1, a[i]) - s;
s[pos] = a[i];
lis[i] = pos;
}
}
cnt = 0;
for(int i = 1; i <= n; i++)
a[i] = -a[i];
for(int i = n; i; i--){
if(!cnt || a[i] > s[cnt]) s[++cnt] = a[i], lds[i] = cnt;
else {
int pos = lower_bound(s + 1, s + cnt + 1, a[i]) - s;
s[pos] = a[i];
lds[i] = pos;
}
}
for(int i = 1; i <= n; i++)
if(lis[i] + lds[i] != cnt + 1) type[i] = 1;
else tot[lis[i]]++;
putchar('A'), putchar(':');
for(int i = 1; i <= n; i++)
if(!type[i] && tot[lis[i]] > 1)
write(i), space;
enter;
putchar('B'), putchar(':');
for(int i = 1; i <= n; i++)
if(!type[i] && tot[lis[i]] == 1)
write(i), space;
enter;
return 0;
}
上一篇:远程IPC种植木马


下一篇:PHP+Ajax 异步通讯注册验证