wuvin
Always take risks!
Toggle navigation
wuvin
主页
实验室的搬砖生活
机器学习
公开的学术内容
公开的其他内容
About Me
归档
标签
友情链接
ZYQN
ihopenot
enigma_aw
hzwer
杨宗翰
BZOJ 2090 [Poi2010] Monotonicity 2
? BZOJ ?
2017-03-19 20:39:14
276
0
0
wuvin
? BZOJ ?
##Description 给出N个正整数a[1..N]，再给出K个关系符号（>、<或=）s[1..k]。 选出一个长度为L的子序列（不要求连续），要求这个子序列的第i项和第i+1项的的大小关系为s[(i-1)mod K+1]。 求出L的最大值。 ##Input 第一行两个正整数，分别表示N和K (N, K <= 500,000)。 第二行给出N个正整数，第i个正整数表示a[i] (a[i] <= 10^6)。 第三行给出K个空格隔开关系符号（>、<或=），第i个表示s[i]。 ##Output 一个正整数，表示L的最大值。 ##Sample Input 7 3 2 4 3 1 3 5 3 < > = ##Sample Output 6 ##HINT 选出的子序列为2 4 3 3 5 3，相邻大小关系分别是< > = < >。 [link](http://www.lydsy.com/JudgeOnline/problem.php?id=2090) 好神啊！根本做不来TAT 第一眼 次方级暴力算法 想了一会 好像可以DP 然后发现看错题了。。。。。。（不要问我为什么那么傻 又读了一遍题，发现还是可以DP 想了一个$n^3$的大暴力 又优化了一下成了$n^2logn$ 然后又想了一个$n^2$的办法 然后就根本没有想到其他的了。。。 想不出来。。。想不出来。。。只有去看题解了 发现是我dp的状态不对只用保留每个数在最终序列中最靠后的可行位置即可 因为是求最长，可以从后往前证明只用保留最靠后的可行位置不会使答案变小。于是就愉快数据结构优化一下就可以了。 P.S:我原来读错题的版本也是一个DP，只不过原有$i$和$i+1$的大小关系不由$i-1$决定，而是由a[$i-1$]的值决定（就是前一个位置的值）。也是可以$nlogn$ DP的。
上一篇:
大整数分解以及素数判定
下一篇:
myy FFT
0
赞
276 人读过
新浪微博
微信
腾讯微博
QQ空间
人人网
提交评论
立即登录
, 发表评论.
没有帐号?
立即注册
0
条评论
More...
文档导航
wuvin
没有帐号? 立即注册