HDU 5696 区间的价值 暴力

分析：枚举以该点为最小值，然后找到最大值，更新，相应数组，至此，把区间分割（因为包含这个最小值点已经枚举过）

然后理解理解，感觉好像挺对的。。。因为后面（即dfs区间变小时）如果再包含最小值节点，也不会比当前枚举的值更大（因为当前找到了最大值）

然后常识可知res[i]>=res[j] j>=i，这是肯定的，小区间肯定比大区间的最优值大，这样扫一遍

有两个功能，1，弥补没有更新的res数组，2，把res数组更新为最优

注：然后我通过窥群，群里的聚聚说是O(nlogn)的，我并不知道是为什么

#include <iostream>

#include <stdio.h>

using namespace std;

typedef long long LL;

const int N=1e5+;

int a[N],n;

LL res[N];

void dfs(int l,int r){

    if(l>r)return;

    if(l==r){res[]=max(res[],1ll*a[l]*a[l]);return;}

    int k1,k2;k1=k2=l;

    for(int i=l;i<=r;++i){

        if(a[i]<a[k1])k1=i;

        if(a[i]>a[k2])k2=i;

    }

    res[r-l+]=max(res[r-l+],1ll*a[k1]*a[k2]);

    dfs(l,k1-);

    dfs(k1+,r);

}

int main(){

    while(~scanf("%d",&n)){

       for(int i=;i<=n;++i)

         scanf("%d",&a[i]),res[i]=;

       dfs(,n);

       for(int i=n-;i>;--i)

         res[i]=max(res[i],res[i+]);

       for(int i=;i<=n;++i)

        printf("%I64d\n",res[i]);

    }

    return ;

}