2016百度之星 hdu 5696 RMQ+單調棧

連結：戳這裡

區間的價值 Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Problem Description

我們定義“區間的價值”為一段區間的最大值*最小值。

一個區間左端點在L，右端點在R，那麼該區間的長度為(R−L+1)。

現在聰明的傑西想要知道，對于長度為k的區間，最大價值的區間價值是多少。

當然，由于這個問題過于簡單。

我們肯定得加強一下。

我們想要知道的是，對于長度為1∼n的區間，最大價值的區間價值分别是多少。

樣例解釋：

長度為1的最優區間為2−2 答案為6∗6

長度為2的最優區間為4−5 答案為4∗4

長度為3的最優區間為2−4 答案為2∗6

長度為4的最優區間為2−5 答案為2∗6

長度為5的最優區間為1−5 答案為1∗6

Input

多組測試資料

第一行一個數n(1≤n≤100000)。

第二行n個正整數(1≤ai≤109)，下标從1開始。

由于某種不可抗力，ai的值将會是1∼109内<b style="color:red;">随機産生</b>的一個數。（除了樣例）

Output

輸出共n行，第i行表示區間長度為i的區間中最大的區間價值。

Sample Input

5

1 6 2 4 4

Sample Output

36

16

12

12

6

思路：

先用單調棧處理出以目前ai為最小值能擴充到的最大的左右區間

然後算出每個ai所在的區間長度的值,已知了目前的最小ai和以ai為最小值的區間[l,r]

直接用RMQ求出[l,r]的區間最大值,則dp[r-l+1]=max(dp[r-l+1],ai*RMQ(l,r))

然後在對于沒算出的長度,繼承一下上面的就可以了  這裡需要滿足dp[len-1]>=dp[len]

代碼：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<vector>
#include <ctime>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<iomanip>
#include<cmath>
#define mst(ss,b) memset((ss),(b),sizeof(ss))
#define maxn 0x3f3f3f3f
#define MAX 1000100
///#pragma comment(linker, "/STACK:102400000,102400000")
typedef long long ll;
typedef unsigned long long ull;
#define INF (1ll<<60)-1
using namespace std;
int n;
int a[200100];
struct node{
    int pos,v;
    node(int pos=0,int v=0):pos(pos),v(v){}
};
stack <node> qu;
int L[200100],R[200100];
int f[200100][20];
int query(int l,int r){
    int m=log(r-l+1)/log(2);
    return max(f[l][m],f[r-(1<<m)+1][m]);
}
ll dp[200100];
int main(){
    while(scanf("%d",&n)!=EOF){
        mst(L,0);
        mst(R,0);
        mst(f,0);
        mst(dp,0);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        while(!qu.empty()) qu.pop();
        qu.push(node(0,0));
        for(int i=1;i<=n;i++){
            while(!qu.empty()){
                node now=qu.top();
                if(a[i]<now.v){
                    R[now.pos]=i-1;
                    qu.pop();
                } else {
                    qu.push(node(i,a[i]));
                    break;
                }
            }
        }
        while(!qu.empty()) {
            node now=qu.top();
            qu.pop();
            R[now.pos]=n;
        }
        qu.push(node(0,0));
        for(int i=n;i>=1;i--){
            while(!qu.empty()){
                node now=qu.top();
                if(a[i]<now.v){
                    L[now.pos]=i+1;
                    qu.pop();
                } else {
                    qu.push(node(i,a[i]));
                    break;
                }
            }
        }
        while(!qu.empty()){
            node now=qu.top();
            qu.pop();
            L[now.pos]=1;
        }
        /*for(int i=1;i<=n;i++) cout<<L[i]<<" ";
        cout<<endl;
        for(int i=1;i<=n;i++) cout<<R[i]<<" ";
        cout<<endl;*/
        for(int i=1;i<=n;i++) f[i][0]=a[i];
        int m=log(n)/log(2);
        for(int i=1;i<=m;i++){
            for(int j=n;j>=1;j--){
                f[j][i]=f[j][i-1];
                if(j+(1<<(i-1))<=n)
                    f[j][i]=max(f[j][i],f[j+(1<<(i-1))][i-1]);
            }
        }
        for(int i=1;i<=n;i++){
            int len=R[i]-L[i]+1;
            dp[len]=max(dp[len],(ll)query(L[i],R[i])*a[i]);
        }
        ll mx=0;
        for(int i=n;i>=1;i--){
            mx=max(dp[i+1],mx);
            dp[i]=max(dp[i],mx);
        }
        for(int i=1;i<=n;i++) cout<<dp[i]<<endl;
    }
    return 0;
}