相关链接
题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4282
神犇题解：http://blog.csdn.net/PoPoQQQ/article/details/48998981
解题报告
首先我们需要得到一个结论：一定存在一组最优解，使得所有的模糊的位置均在LIS中
现在我们来证明一下这个结论：
考虑如果有一组最优解中存在一个模糊的位置不在最优解中
那么讲这个模糊的位置换成后面的第一个确定位置的数即可，这样不会使答案变劣
于是我们就假设一个确定的位置的前缀中有a个不确定位置
那么我们把该确定位置的值减去a（相当于把那a个不确定位置在值域上留出位置）
然后对确定的串做一次LIS，然后加上不确定位置的个数即可
Code
我写LIS一直用的BIT，但PoPoQQQ大爷的LIS似乎更加优雅
他是直接维护一个最优的LIS，然后每一次lower_bound就可以了！
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 200000+9;
int n,m,tot,vout,_hash[N],f[N],arr[N];
char pat[10];
class Fenwick_Tree{
int mx[N];
public:
inline void modify(int p, int v) {
for (int i=p;i<=tot;i+=lowbit(i))
mx[i] = max(mx[i], v);
}
inline int query(int p) {
int ret = 0;
for (int i=p-1;i;i-=lowbit(i))
ret = max(ret, mx[i]);
return ret;
}
private:
inline int lowbit(int x) {
return x & (-x);
}
}BIT;
inline int read() {
char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}
int main() {
n = read();
for (int i=1;i<=n;++i) {
scanf("%s",pat+1);
if (pat[1] == 'K') {
arr[++tot] = read() - m;
_hash[tot] = arr[tot];
} else ++m;
}
n = tot; sort(_hash+1, _hash+1+tot);
tot = unique(_hash+1, _hash+1+tot) - _hash - 1;
for (int i=1;i<=n;i++) {
arr[i] = lower_bound(_hash+1, _hash+1+tot, arr[i]) - _hash;
f[i] = BIT.query(arr[i]) + 1;
vout = max(f[i], vout);
BIT.modify(arr[i], f[i]);
}
printf("%d\n",vout + m);
return 0;
}
