|
|
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2227
  /**//*
 题意：
给定N(N <= 100000)个数字ai，找出这个序列中有多少非递减序列。
解法：
树状数组 + 动态规划
思路：
如果n的值小于等于1000，我们可以用动态规划来解，dp[i]表示
到第i个位置能够找到的非递减序列的解的数量，那么有状态转移方程
dp[i] = sum{ dp[j], j<i, a[j]<=a[i] }，这个时间复杂度是O(n^2)
，但是n很大，所以不能采用，但是我们观察到这个转移方程是以求和
的形式出现，并且有一个限制条件就是a[j] <= a[i]，那么如果我们把
数字映射到下标，就可以轻松的通过树状数组的成段求和来统计了。
具体做法是：由于数字较大，我们可以先将所有数字离散化，这样
每个数字就有一个 <= n 的标号，然后这个标号就可以对应树状数组的
下标了，每次从左往右在树状数组中统计比当前数小或者相等的数的个
数，然后将当前数字（离散后的数字）插入到树状数组中，循环结束，
累加和就是最后的答案了。
。
 */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef unsigned int ui;
typedef __int64 ll;
#define maxn 100010
#define mod 1000000007
int n;
ui val[maxn], t[maxn];
ll c[maxn];
int tot;
int lowbit(int x)  {
return x & (-x);
}
void add(int pos, ll v) {
  while(pos <= tot) {
c[pos] += v; if(c[pos] >= mod ) c[pos] %= mod;
pos += lowbit(pos);
 }
}
ll sum(int pos) {
int s = 0;
while(pos >= 1) {
s += c[pos]; if(s >= mod ) s %= mod;
pos -= lowbit(pos);
}
return s;
}
int Bin(ui v) {
int l = 1;
int r = tot;
while(l <= r) {
int m = (l + r) >> 1;
if(v == t[m])
return m;
if(v > t[m])
l = m + 1;
else
r = m - 1;
}
}
int main() {
int i;
while(scanf("%d", &n) != EOF) {
for(i = 0; i < n; i++) {
scanf("%u", &val[i]);
t[i+1] = val[i];
}
tot = 0;
sort(t+1, t+1+n);
for(i = 1; i <= n; i++) {
if(i==1 || t[i] != t[i-1]) {
t[++tot] = t[i];
c[tot] = 0;
}
}
for(i = 0; i < n; i++) {
val[i] = Bin(val[i]);
}
ll ans = 0;
add(1, 1);
for(i = 0; i < n; i++) {
ll x = sum(val[i]);
ans += x; if(ans >= mod) ans %= mod;
add(val[i], x);
}
printf("%d\n", (int)ans);
}
return 0;
}
|