BZOJ 5427: 最长上升子序列&&4282: 慎二的随机数列（DP）
Posted On 2018年10月11日
Description
现在给你一个长度为n的整数序列，其中有一些数已经模糊不清了，现在请你任意确定这些整数的值，
使得最长上升子序列最长。（为何最长呢？因为hxy向来对自己的rp很有信心）
Input
第一行一个正整数n
接下来n行第i行格式如下
K x：表示第i个数可以辨认且这个数为x
N：表示第i个数一个已经辨认不清了
n<=100000,|x|<=10^9
Output
一个正整数代表最长上升子序列最长是多少
Sample Input
4
K 1
N
K 2
K 3
K 1
N
K 2
K 3
Sample Output
3
【样例说明】
当序列为1 1 2 3 （也可以1 2 2 3,1 0 2 3……）
时最长上升子序列最长，为3
【样例说明】
当序列为1 1 2 3 （也可以1 2 2 3,1 0 2 3……）
时最长上升子序列最长，为3
HINT
Source
Solution
令\(f[i]\)表示当前长度为\(i\)的最长上升子序列最后一位的最小值
当该位不确定时显然总答案加一，所有\(f[i]++\)并左移一位
确定时直接二分更新即可
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
#include <cstdio> #include <cstring> #include <vector> #include <cmath> #include <algorithm> #include <bitset> #include <queue> #include <set> #include <iostream> typedef long long ll; using namespace std; bool flag; const int maxn=1e5+100; char s[maxn*10],*c; inline int read() { int f=1,k=0; while (*c<'0'||*c>'9')*c++=='-'&&(f=-1); while (*c>='0'&&*c<='9')k=k*10+*c++-'0'; return k*f; } int next; int f[maxn]; signed main() { fread(c=s,1,sizeof(s),stdin); int n=read(),up=0,delta=0; f[0]=-1e9; for (int i=1;i<=n;i++) { while ('A'>*c||*c>'Z')++c; if (*c++=='K') { int l=0,r=up,mid,v=read(); while (l<r) { mid=(l+r)>>1; if (f[mid]+delta<v)l=mid+1;else r=mid; } if (f[l]+delta<v)f[++up]=v-delta; else f[l]=v-delta; } else ++delta; } printf("%d\n",up+delta); } |
Subscribe
0 评论