[BOJ 8897] Slicing Tree

 2012 ACM-ICPC Daejeon regional 의 기출문제입니다. 백준 8897 에서 채점할 수 있습니다.

풀이 )

 

 동적 계획법으로 해결할 수 있습니다. 

vector<PII> dp[i] =  i 노드가 가질 수 있는 '유효한' 사각형들의 배열. 오름차순으로 정렬되어 있음.

(PII 는 pair<long long, long long>입니다.)

(dp[i][j].first = 넓이, dp[i][j].second = 높이)

 여기에서 유효하다는 건, W <= dp[i][j].first && H <= dp[i][j].second 를 만족하는 다른 사각형 (W,H) 가 없다는 뜻입니다. 이런 (W,H)가 있으면 dp[i][j]를 저장할 필요가 없습니다.

 쉽게 생각하면 이런 사각형이 dp[i] 하나당 50만개 쯤 생기면 어쩌나 걱정할 수도 있지만, 이 dp[]를 구하는 과정을 보면 유효한 사각형은 그리 많지 않음을 알 수 있습니다. 일단 이 dp[]들을 구하는 방법을 알아보겠습니다.

 우선, dp[1] ~ dp[n] 까지는 입력으로 들어온 w,h로 처리할 수 있습니다. PII(w,h)와 PII(h,w)를 저장하면 됩니다. (번호는 입력으로 들어오는 사각형들은 dp[1] ~ dp[n], 그리고 H나 L로 합쳐서 생기는 노드들인 노드 생성 순서대로 dp[n+1], dp[n+2], ..., dp[2*n-1]에 저장하도록 번호를 부여하였습니다.)

  그 다음, H 혹은 L이 들어왔을 때 두 dp[]를 합쳐서 하나의 dp[]로 만드는 함수를 만들어야 합니다. H일 경우엔 아래와 같이 구할 수 있습니다.

// code by RiKang, weeklyps.com
 
void get_dp(int v1, int v2){
    int j=-1;
    for(int i=0; i<dp[v1].size(); i++){
        while(j+1<dp[v2].size() && dp[v2][j+1].first <= dp[v1][i].first)
            j++;
        if(j!=-1)
            dp[num].push_back(PII(dp[v1][i].first, dp[v1][i].second+dp[v2][j].second));
    }
}
 
void merge(int v1, int v2){ // dp[v1]+dp[v2] -> dp[num]!
    get_dp(v1,v2);
    get_dp(v2,v1);
    tuning(dp[num]); // 유효한 사각형만 남기도록 튜닝
}

 dp[v1][i] 와 dp[v2][j] 를 합치면 (first중 최대값, second 의 합) 이 됨은 당연합니다. 그런데 dp[v1][i].first >= dp[v2][j].first 인 경우들을 생각해보면, 이 부등식을 만족하는 j중에서 dp[v2][j].second 가 가장 작은 경우만 고려해도 됨을 알 수 있습니다. second의 합이 최소가 되는게 최선이기 때문입니다. 이점에서 착안해 위와 같이 구현할 수 있습니다.

 그리고 이런 점 때문에, dp[num].size() <= dp[v1].size()+dp[v2].size() 임을 알 수 있습니다. 결국 모든 dp[].size()를 합해도 O(n^2)임이 증명됩니다.

 L의 경우엔 swap(dp[v1].first, dp[v1].second), swap(dp[v2].first, dp[v2].second) 를 해주고 H와 똑같이 처리한 이후, swap(dp[num].first, dp[num].second)를 해주면 됩니다. 자세한 구현은 아래의 코드를 참고해 주시기 바랍니다.

 최종 코드 )

// code by RiKang, weeklyps.com
// 2012 ACM-ICPC Daejeon regional - J
// BOJ 8897 Slicing Tree
 
#include <bits/stdc++.h>
#define PII pair<long long, long long>
using namespace::std;
 
int n, num;
char a[105];
stack<int> st;
vector<PII> dp[2005];
 
void v_swap(vector<PII>& vp){
    for(int i=0; i<vp.size(); i++)
        swap(vp[i].first,vp[i].second);
}
 
void get_dp(int v1, int v2){
    int j=-1;
    for(int i=0; i<dp[v1].size(); i++){
        while(j+1<dp[v2].size() && dp[v2][j+1].first <= dp[v1][i].first)
            j++;
        if(j!=-1)
            dp[num].push_back(PII(dp[v1][i].first, dp[v1][i].second+dp[v2][j].second));
    }
}
 
void tuning(vector<PII>& vp){
    sort(vp.begin(), vp.end());
    vector<PII> v;
    long long mi = (long long)1<<60;
    for(int i=0; i<vp.size(); i++){
        if(mi > vp[i].second){
            v.push_back(vp[i]);
            mi = vp[i].second;
        }
    }
    vp.clear();
    for(auto p: v)
        vp.push_back(p);
}
 
void merge(int v1, int v2){ // dp[v1]+dp[v2] -> dp[num]!
    get_dp(v1,v2);
    get_dp(v2,v1);
    tuning(dp[num]);
}
 
void solve(){
    scanf("%d",&n);
    for(int i=1; i<=2*n; i++) dp[i].clear();
    for(int i=1; i<=n; i++){
        int w,h;
        scanf("%d %d",&w,&h);
        if(w>h) swap(w,h);
        dp[i].push_back(PII(w,h));
        if(w!=h)
            dp[i].push_back(PII(h,w));
    }
    num=n+1;
    for(int i=1; i<2*n; i++){
        scanf("%s",a);
        if(a[0]=='H'){
            int v1 = st.top();
            st.pop();
            int v2 = st.top();
            st.pop();
            
            merge(v1,v2);
            
            st.push(num);
            num++;
        }
        else if(a[0]=='V'){
            int v1 = st.top();
            st.pop();
            int v2 = st.top();
            st.pop();
            v_swap(dp[v1]);
            tuning(dp[v1]);
            v_swap(dp[v2]);
            tuning(dp[v2]);
            
            merge(v1,v2);
            
            v_swap(dp[num]);
            tuning(dp[num]);
            st.push(num);
            num++;
        }
        else{
            int o = 0;
            for(int i=0; i<strlen(a); i++){
                o=o*10+a[i]-'0';
            }
            st.push(o);
        }
    }
    num=st.top();
    long long ans = (long long)1<<60;
    for(int i=0; i<dp[num].size(); i++)
        ans = min(ans, (long long)dp[num][i].first*dp[num][i].second);
    printf("%lld\n",ans);
}
 
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        solve();
    }
    return 0;
}