HDU 3450 Counting Sequences（DP + 树状数组）

2015-12-26 05:13 浏览次数:9255 我来说两句(0) 大中小

　　题目链接：点击打开链接

　　题目大意：统计满足相邻两个数之差不超过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
#include
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int mod = 9901;
const int INF = 1000000000;
const int maxn = 100000 + 10;
ll T,n,m,e,d[maxn],bit[maxn],kase = 0,a[maxn],b[maxn];
ll sum(ll x) {
ll ans = 0;
while(x > 0) {
ans = (ans + bit[x])%mod;
x -= x & -x;
}
return ans;
}
void add(ll x, ll dd) {
dd %= mod;
while(x <= n) {
bit[x] = (bit[x] + dd)%mod;
x += x & -x;
}
}
int main() {
while(~scanf("%I64d%I64d",&n,&e)) {
memset(bit, 0, (n+1)*sizeof(ll));
ll maxv = 0;
for(int i=1;i<=n;i++) {
scanf("%I64d",&a[i]);
b[i] = a[i];
maxv = max(maxv, a[i]);
}
sort(b+1, b+n+1);
int len = unique(b+1,b+n+1) - b - 1;
for(int i=1;i<=n;i++) {
ll l = lower_bound(b+1,b+len+1,a[i]-e) - b - 1;
ll r = lower_bound(b+1,b+len+1,a[i]+e) - b;
ll v = lower_bound(b+1,b+len+1,a[i]) - b;
if(r > len || b[r] > a[i]+e) --r;
d[i] = (sum(r) - sum(l) + mod) % mod;
add(v, d[i]+1);
}
ll ans = 0;
for(int i=1;i<=n;i++) {
ans = (ans + d[i])%mod;
}
printf("%I64d\n",ans);
}
return 0;
}