当前位置: 爱尖刀 > 首页安全 > 技术文章 > 正文

HDU 3450 Counting Sequences(DP + 树状数组)

2015-12-26 05:13 浏览次数:7058 我来说两句(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;
}


来源:红黑联盟

[广告]赞助链接:

知安,互联网产品安全医院:http://www.knowsafe.com
舆情监测,互联网舆情首选查舆情:http://www.chayuqing.com/
爱尖刀科技,关注企业数据与安全:http://www.ijiandao.com

关注公众号:Mcbang_com 了解更多精彩,关注:chayuqing_com 娱乐资讯早知道!
收藏 分享 发布者: admin |
看完这篇文章,你的感受如何?


伤心


无视


惊讶


流汗


赞同


路过
热点聚焦
更多>>
情凝中秋,乐在团圆 中秋节又称团圆节,是从古代至今,对远方亲人思念之情的体现;也是东方 ... [详细]
传递爱心 帮助需要的人 中国红十字已不能信任,民政系统变的自私,在这样的环境下,很多需 ... [详细]
【D盾】- 携手啊D共推《 [详细]
父亲节(Father's D 温家宝:父爱,如大海般深沉而宽广。 我们的力量出自与父亲,我们的 ... [详细]
祝高考学子凯旋而归 明后两天,高中三年的最后两天,也是将会影响命运的两天! 3年=1095天 ... [详细]

Archiver|网络尖刀 ( 京ICP备14006288号-3 )  

GMT+8, 2017-5-27 06:41 , Processed in 0.186421 second(s), 20 queries , Gzip On.

请勿发布违反中华人民共和国法律法规的言论
郑重声明:本站会员观点不代表【网络尖刀】论坛官方立场。

Copyright© 2006-2016 IjianDao.Com All rights reserved. 网络尖刀 版权所有

回顶部