HDU 2836 Traversal 簡單DP + 樹狀數組

題意：給你一個序列，問相鄰兩數高度差絕對值小于等于H的子序列有多少個。

dp[i]表示以i為結尾的子序列有多少，易知狀態轉移方程為：dp[i] = sum( dp[j] ) + 1;( abs( height[i] - height[j] ) <= H )

由abs( height[i] - height[j] ) <= H 可得?height[i] - H <= height[j] <= height[i] + H

將序列中的數離散化，每個height對應一個id, 用樹狀數組求區間[?height[i] - H的id, height[i] + H的id ]內dp[j]的和，并且每次把新得到的dp[i]更新到樹狀數組中height[i]的id對應的位置。

?

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>

using namespace std;

const int MAXN = 100100;
const int MOD = 9901;

int dp[MAXN];
int height[MAXN];
int num[MAXN];
int C[MAXN];
int n, d;

int lowbit( int x )
{
    return x & ( -x );
}

int Query( int x )
{
    int res = 0;
    while ( x > 0 )
    {
        res += C[x];
        res %= MOD;
        x -= lowbit(x);
    }
    return res;
}

void Add( int x, int v )
{
    while ( x <= n )
    {
        C[x] += v;
        C[x] %= MOD;
        x += lowbit(x);
    }
    return;
}

int main()
{
    while ( ~scanf( "%d%d", &n, &d ) )
    {
        for ( int i = 1; i <= n; ++i )
        {
            scanf( "%d", &height[i] );
            num[i] = height[i];
        }

        sort( num + 1, num + n + 1 );
        int cnt = unique( num + 1, num + n + 1 ) - num - 1;

        memset( C, 0, sizeof(C) );
        int ans = 0;
        dp[0] = 0;
        for ( int i = 1; i <= n; ++i )
        {
            int id = lower_bound( num + 1, num + cnt + 1, height[i] ) - num;
            int left = lower_bound( num + 1, num + cnt + 1, height[i] - d ) - num;
            int right = upper_bound( num + 1, num + cnt + 1, height[i] + d ) - num - 1;
            dp[i] = ( Query( right ) - Query( left - 1 ) + 1 ) % MOD;
            ans += dp[i];
            Add( id, dp[i] );
        }

        if ( ans >= n ) ans -= n;
        else ans = 0;
        printf("%d\n", ans % MOD );
    }
    return 0;
}

?