【USACO】 Balanced Lineup

【タイトルリンク】
クリックしてリンクを開く
【アルゴリズム】
これは古典的な最値クエリ(RMQ)の問題です.私たちはまず線分の木を考えます.しかし、もっと速い方法はありませんか?このような問題に対して,STテーブル(疎テーブル)アルゴリズムを用いて解くことができる.疎表アルゴリズム.実は動的計画のアルゴリズムでもある.まず前処理をして、それからO(1)は答えを求めます.設計状態:f[i][j]はi番目の数から2^j番目の次数(i番目の数を含む)が連続していることを示し、中の(最大または最小値)では状態遷移方程式は何でしょうか.私たちは2^jが2つの2^(j-1)に分解できることを知っているので、f[i][j]=maxまたはmin(f[i][j-1],f[i+2^(j-1)][j-1])は前処理を完了し、私たちはどのように検索すればいいのでしょうか.まず,2^log(x)>x/2がxを2^i+kの形式で表すと,log(x)=iが得られる:2^i>2^(i-1)+k/2^(i-1)>k/2^i>k 2^iがkより大きいことを知って成立することを実証した.だからクエリ(最大または最小値)では、2^log(x)の長さの区間を2つ探して最大最小値を求めるだけでいいのです
この問題はST表裸問題ともいえる
【コード】
         

#include

using namespace std;

int i,j,N,M,k,x,y;
int a[50005],f_max[50005][105],f_min[50005][105];

int main() {
                
        scanf("%d%d",&N,&M);
        for (i = 1; i <= N; i++) {
                scanf("%d",&a[i]);
                f_max[i][0] = f_min[i][0] = a[i];
        }
        
        for (i = N; i >= 1; i--) {
                for (j = 1; i + (1<1 <= N; j++) {
                        f_max[i][j] = max(f_max[i][j-1],f_max[i+(1<1))][j-1]);
                        f_min[i][j] = min(f_min[i][j-1],f_min[i+(1<1))][j-1]);
                }    
        }
        
        for (i = 1; i <= M; i++) {
                scanf("%d%d",&x,&y);
                k = (int)(log(y - x + 1) / log(2.0));
                printf("%d
",max(f_max[x][k],f_max[y-(1<1][k]) - min(f_min[x][k],f_min[y-(1<1][k]));
        }
        
        return 0;
    
}

 
転載先:https://www.cnblogs.com/evenbao/p/9196428.html