fzoj 2236 第十四個目标 （樹狀數組&LIS&dp）好題

 Problem 2236 第十四個目标

Accept: 14    Submit: 26

Time Limit: 1000 mSec    Memory Limit : 32768 KB

 Problem Description

目暮警官、妃英裡、阿笠博士等人接連遭到不明身份之人的暗算，柯南追蹤傷害阿笠博士的兇手，根據幾起案件現場留下的線索發現兇手按照撲克牌的順序行兇。在經過一系列的推理後，柯南發現受害者的名字均包含撲克牌的數值，且撲克牌的大小是嚴格遞增的，此外遇害者與毛利小五郎有關。

為了避免下一個遇害者的出現，柯南将可能遭到暗算的人中的數字按關聯程度排列了出來，即順序不可改變。柯南需要知道共有多少種可能結果，滿足受害人名字出現的數字嚴格遞增，但是他柯南要找出關鍵的證據所在，是以這個任務就交給你了。

(如果你看不懂上面在說什麼，這題是求一個數列中嚴格遞增子序列的個數。比如數列(1,3,2)的嚴格遞增子序列有(1)、(3)、(2)、(1,3)、(1,2)，共5個。長得一樣的但是位置不同的算不同的子序列，比如數列(3,3)的答案是2。)

 Input

多組資料(<=10)，處理到EOF。

第一行輸入正整數N(N≤100 000)，表示共有N個人。

第二行共有N個整數Ai(1≤Ai≤10^9)，表示第i個人名字中的數字。

 Output

每組資料輸出一個整數，表示所有可能的結果。由于結果可能較大，對1 000 000 007取模後輸出。

 Sample Input

3 1 3 2

 Sample Output

5

 Source

福州大學第十三屆程式設計競賽 //分析： 如果n的值比較小，那麼就是一個純粹的dp題。設dp[i]表示以a[i]為結尾非降子序列的個數，其狀态轉移方程為：

最後ans = sigma(dp[i]) 其中(1 <= i <= n)

可以看出，這樣做的時間複雜度是

，很顯然不能這樣做。

那麼實際上，我們看到

會想到逆序數，自然也會想到求逆序數最經典的做法就是樹狀數組，是以問題可以轉化為求逆序數的對數，那麼我們可以利用dp的思想遞推下去，最終求得答案，可以看出這樣做的時間複雜度為

。

#include <iostream>
#include <string.h>
#include <algorithm>
#include <stdio.h>
using namespace std;
const int N = 100005;
const int MOD = 1000000007;
struct node
{
    int id,val;
};
int n;
node a[N];
int aa[N],c[N],t[N];
bool cmp(node a,node b)
{
    return a.val < b.val;
}
int Lowbit(int x)
{
    return x & (-x);
}
void Update(int t,int val)
{
    for(int i=t; i<=n; i+=Lowbit(i))
    {
        c[i] += val;
        c[i] %= MOD;
    }
}
int getSum(int x)
{
    int ans = 0;
    for(int i=x; i>0; i-=Lowbit(i))
    {
        ans += c[i];
        ans %= MOD;
    }
    return ans;
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        memset(c,0,sizeof(c));
        memset(aa,0,sizeof(aa));
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i].val);
            a[i].id = i;
        }
        sort(a+1,a+n+1,cmp);
        aa[a[1].id] = 1;
        for(int i=2;i<=n;i++)
        {
            if(a[i].val != a[i-1].val)
                aa[a[i].id] = i;
            else
                aa[a[i].id] = aa[a[i-1].id];
        }
        for(int i=1;i<=n;i++)
        {
            t[i] = getSum(aa[i]-1);
            Update(aa[i],t[i]+1);
        }
        printf("%d\n",getSum(n));
    }
    return 0;
}