hiho學習日記：hiho一下 第十六周（RMQ_ST)

http://hihocoder.com/contest/hiho16/problems

線段樹好像過不了，而且還卡cin，cout -_-

ST算法就是用二維數組存儲目前位置的 2 j 2^j 2j的區間的最小值

而且由遞推公式 d p [ i ] [ j ] = m i n ( d p [ i ] [ j − 1 ] , d p [ i + 2 ( j − 1 ) ] [ j − 1 ] ) dp[i][j] = min(dp[i][j - 1], dp[i + 2^(j - 1)][j - 1]) dp[i][j]=min(dp[i][j−1],dp[i+2(j−1)][j−1])

那麼求出dp數組的話，那麼就可解

AC代碼：

c

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e6 + 5;
const int Mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
#define LL long long

int dp[maxn][30];

int main()
{
    int n;
    scanf("%d", &n);
    memset(dp, INF, sizeof(dp));
    for (int i = 1; i <= n; i ++)
        scanf("%d", &dp[i][0]);
    int base = 1;
    for (int i = 1; (base << 1) <= n; i ++) {
        for (int j = 1; j + base <= n; j ++) {
            dp[j][i] = min(dp[j][i - 1], dp[j + base][i - 1]);
        }
        base <<= 1;
    }

    int q;
    scanf("%d", &q);
    while(q --) {
        int L, R;
        scanf("%d %d", &L, &R);
        int p = log2(R - L + 1), k = 1 << p;
        int ans = min(dp[L][p], dp[R - k + 1][p]);
        printf("%d\n", ans);
    }
    return 0;
}