BOJ)15673 헤븐스 키친2

문제 :http://icpc.me/15673

n개의 수열이 주어질 때, 연속 된 두 구간을 선정을 한다. 두 구간을 a,b라하면

구간 a의 합과 구간 b의 합의 곱의 최댓값을 구하는 문제이다.

생각해보면 구간 a의 합과 구간 b의 합의 최솟값들을 곱하는 경우와, 구간 a의 합과 구간 b의 합의 최댓값들을 곱하는 경우가 답의 후보가 됨을 알 수 있다. 

구간 a가 i~j 구간 b가 k~l 이라고 해보자.

k를 고정시킨 뒤 생각해보면 구간 k~l의 합은 psum[l]-psum[k-1]이므로, k보다 크거나 같은 범위의 psum의 최댓값과 최솟값을 가지고 있으면, 구간 b의 최댓값과 최솟값을 구할 수 있다.

그럼 i~j 구간의 최댓값과 최솟값은 어떻게 처리할 수 있을까?

구간 i~j의 합은 psum[j]-psum[i-1]이 된다. 하지만 모든 i,j에 대하여 구한다면 너무 많은 시간이 걸릴 것이다.

따라서 이 구간을 처리하기 위해 두가지 dp를 정의한다.

dp1[x]: ?~x구간의 합의 최댓값

dp2[x]: ?~x구간의 합의 최솟값

이렇게 정의를 해주면 dp테이블을 채울 때 오른쪽 부분이 고정되므로 x보다 작은 인덱스의 psum중 최댓값과 최솟값을 구하는것으로 dp테이블들을 채워줄 수 있다.

모든 dp테이블을 채우고 나서 다시 k를 고정시켰을 때 i~j의 최댓값 최솟값 문제로 돌아가면

이제 i~j의 최댓값 최솟값을 구하는 문제는 k보다 작은 인덱스를 가진 dp1들의 최댓값과 dp2들의 최솟값을 확인하는것으로 변형된다.

모든 전처리를 해준 뒤 계산을 해주면 시간 복잡도는 O(NlogN)이 된다.

소스코드를 첨부한다. 최대 최소를 구하는 계산은 set과 multiset을 이용했다.

#include <cstdio>
#include <algorithm>
#include <set>
using namespace std;
typedef long long ll;
ll n,a[100010],p[100010],dp1[100010],dp2[100010],res;
set<ll> maxmin,maxx,minn;
multiset<ll> cal;
int main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    for(int i=1;i<=n;i++)p[i]=p[i-1]+a[i];
    maxmin.insert(0);
    for(int i=1;i<=n;i++){
        dp1[i]=p[i]-*maxmin.begin();
        auto it=maxmin.end();
        it--;
        dp2[i]=p[i]-*it;
        maxmin.insert(p[i]);
    }
    res=-1e18;
    maxx.insert(dp1[1]);
    minn.insert(dp2[1]);
    for(int i=2;i<=n;i++)cal.insert(p[i]);
    for(int i=2;i<=n;i++){
        ll mincurr=-p[i-1]+*cal.begin();
        auto it=cal.end();
        it--;
        ll maxcurr=-p[i-1]+*it;
        it=maxx.end();
        it--;
        res=max(res,max(mincurr*(*minn.begin()),maxcurr*(*it)));
        cal.erase(cal.find(p[i]));
        maxx.insert(dp1[i]);
        minn.insert(dp2[i]);
    }
    printf("%lld\n",res);
    return 0;
}