题目链接:点击打开链接
题目大意: 统计满足相邻两个数之差不超过d的子序列个数。
我们不难想到一个O(n^2)的DP算法 : 对于每一个i, d[i]表示 以i结尾的子序列个数。 那么它将转移到所有满足(j >= 1 && j < i && abs(a[j]-a[i])<=d)的d[j] 。
但是由于n太大了, 这样显然会超时, 那么我们来想想如何优化这个算法: 可以发现, 对于每个d[i], 其累加的部分是一个(a[i] - d, a[i] + d)的范围内的且在i之前出现过的所有d[j]。 这恰恰符合树状数组的特点: 求连续和、单点更新 。
所以我们不难想到每次更新完d[i] 之后, 在a[i]这个位置上增加d[i]+1。 但是该题没有给a[i]的数据范围, 得到WA之后证明, 数据应该很大, 数组开不下。 那么我们只需要离散化一下, 将数据一一映射到1~n的范围内就好了。然后用二分查找找到映射后的代码,用树状数组求解。
离散化的一个比较简单易行的方法就是用另一个数组b复制a,然后对b进行排序去重,那么此时b的下标就是对数组a映射后的值,用二分查找可以很容易的找到。
复杂度O(n*logn)。
细节参见代码:
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
来源:红黑联盟
关注公众号:拾黑(shiheibook)了解更多!