海带头又上线了QwQ~
这是一个奇怪的lis问题
显然一定存在一种最优答案使所有辨认不清的数都在答案中。
【为什么呢】因为你完全可以用一个‘N’来替换一个‘K’啊QwQ~
那么在选完所有‘N’之后，一个为‘K’的数的值val[i]就可以理解为val[i]-num，num指它之前‘N’的个数（因为是严格单调增的）
然后就是裸的lis啦~，记得答案要加上‘N’的个数。
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int Mx=;
int n,num,ans,c[Mx],f[Mx],d[Mx];
void read()
{
scanf("%d",&n);int cnt=;
for(int i=;i<=n;i++)
{
char ch;bool jud=;
while(scanf("%c",&ch))
{
if(ch=='K') { jud=; break;}
else if(ch=='N') { num++;break; }
}
if(jud==) { scanf("%d",&c[++cnt]);c[cnt]-=num; }
}
n=cnt;
}
void solve()
{
memset(f,0x3f,sizeof f);
for(int i=;i<=n;i++)
{
int pos=lower_bound(f+,f+n+,c[i])-f;
ans=max(ans,pos);f[pos]=c[i];
}
cout<<ans+num<<endl;
}
int main()
{
read();
solve();
return ;
}