Day2 T2 DP优化可过？

dp[i][0] = max(dp[i-1][0],dp[j][1] + 1,1) h[j] > h[i]
dp[i][1] = max(dp[i-1][1],dp[j][0] + 1,1) h[j] < h[i]

我就是这么写的。。。离散化后两个zkw线段树按奇偶性查。。

不感兴趣

开通SVIP免广告

知道最长上升子序列的某种伪单调队列算法吗
可以轻松过O(n)

本蒟蒻表示SB一样写了个DP然后离散化h数组，用两棵权值线段树查询最大值。。。

树状数组即可。。

不用优化啊，开两个数组贪心压常数即可

下载贴吧APP
看高清直播、视频！

分享到: