题意

给出一个长度为n的序列&＃xff0c;有一些位置可以放任意的数&＃xff0c;问最长上升序列的长度。
n<&＃61;100000

分析

dalao们的做法都好劲啊&＃xff0c;就我的做法最暴力。。。

考虑用二分求lis做法&＃xff0c;用一个f[i]维护长度为i的最长上升序列的结尾的最小值。若当前要处理的位置是有数字的则直接处理&＃xff0c;否则设当前的最长上升序列长度为maxlen&＃xff0c;则f[i]&＃61;f[i-1]&＃43;1 (1<&＃61;i<&＃61;maxlen&＃43;1)&＃xff0c;那么我们可以考虑用一个变量add表示f数组中的每一个数都被加上了add&＃xff0c;然后把整个序列向后移一位即可。我的处理方法是维护一个pos表示f序列的结尾下标&＃xff0c;那么开头下标就是pos-maxlen&＃43;1了。

一次AC吼爽啊&＃xff01;&＃xff01;&＃xff01;

代码

#include
#include
#include
#include
#include
#define N 200005
#define inf 0x7fffffff
using namespace std;int n,maxlen,add,pos,f[N],a[N];int ef(int x)
{int l&＃61;pos-maxlen&＃43;1,r&＃61;pos;while (l<&＃61;r){int mid&＃61;(l&＃43;r)/2;if (f[mid]&＃43;add<x) l&＃61;mid&＃43;1;else r&＃61;mid-1;}return l-1;
}int main()
{scanf("%d",&n);for (int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){char ch[2];scanf("%s",ch);if (ch[0]&＃61;&＃61;&＃39;N&＃39;) a[i]&＃61;inf;else scanf("%d",&a[i]);}pos&＃61;n;maxlen&＃61;add&＃61;0;for (int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)if (a[i]&＃61;&＃61;inf){add&＃43;&＃43;;maxlen&＃43;&＃43;;f[pos-maxlen&＃43;1]&＃61;-inf;}else{int x&＃61;ef(a[i]),len&＃61;x-pos&＃43;maxlen&＃43;1;if (len>maxlen){maxlen&＃61;len;pos&＃43;&＃43;;f[pos]&＃61;a[i]-add;}else f[x&＃43;1]&＃61;min(f[x&＃43;1],a[i]-add);}printf("%d",maxlen);return 0;
}