51nod 1062 && URAL 1079 Maximum RMQ

题目：

https://vjudge.net/problem/URAL-1079

题意：

有这样一个序列a：

• a0=0
• a1=1
• a2i=ai
• a2i+1=ai+ai+1
  输入一个数n，求a[0]−a[n]中最大的数。

思路：

先打表出所有的序列，然后rmq求解即可

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 100000 + 10, MOD = 1000000007;

int a[N], dp[20][N];
void table()
{
    a[0] = 0, a[1] = 1;
    for(int i = 1; i <= 50000; i++)
        a[2*i] = a[i], a[2*i+1] = a[i] + a[i+1];
}
void ST(int n)
{
    for(int i = 1; i <= n; i++)
        dp[0][i] = a[i-1];
    for(int i = 1; (1<<i) <= n; i++)
        for(int j = 1; j <= n - (1<<i) + 1; j++)
            dp[i][j] = max(dp[i-1][j], dp[i-1][j+(1<<(i-1))]);
}
int RMQ(int l, int r)
{
    int k = log2(r - l + 1);
    return max(dp[k][l], dp[k][r-(1<<k)+1]);
}
int main()
{
    table();
    ST(100000 + 1);
    int t, n;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        printf("%d\n", RMQ(1, n + 1));
    }
    return 0;
}