|
|
題目鏈接：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;
}
|