[ZJ] b220: 5. 蛋糕師傅的煩惱

#include<stdio.h>
#include<string.h>
#include<stack>
#include<vector>
#include<algorithm>
using namespace std;
char s[1000];
struct P{
    int x,y;
}area[1005];
stack<vector<P> > sta;
vector<P> in,a1,a2;
int is[2505][2505];
char c[5];
int main(){
    int n=0,i,j,k,len,val,flag=1,tmp,X,Y,ans=999999999;
    gets(&s[1]);
    s[0]=' ';
    len=strlen(s);
    for(i=0;i<len;i++)
        if(s[i]=='V' ||s[i]=='H')
            n++;
    n++;
    for(i=0;i<n;i++){
        scanf("%d%d%d",&k,&X,&Y);
        area[k]=(P){X,Y};
    }
    for(i=1;i<len;i++){
        if(s[i-1]==' ' && s[i]!=' '){
            if(s[i]=='H'){
                a1=sta.top();
                sta.pop();
                a2=sta.top();
                sta.pop();
                memset(is,0,sizeof(is));in.clear();
                for(j=0;j<a1.size();j++)
                    for(k=0;k<a2.size();k++){
                        Y=a1[j].y+a2[k].y;
                        X=max(a1[j].x,a2[k].x);
                        if(is[X][Y]==0){
                            is[X][Y]=1;

                            in.push_back((P){X,Y});
                        }
                    }
                sta.push(in);
            }
            else if(s[i]=='V'){
                a1=sta.top();
                sta.pop();
                a2=sta.top();
                sta.pop();
                memset(is,0,sizeof(is));in.clear();
                for(j=0;j<a1.size();j++)
                    for(k=0;k<a2.size();k++){
                        X=a1[j].x+a2[k].x;
                        Y=max(a1[j].y,a2[k].y);
                        if(is[X][Y]==0){
                            is[X][Y]=1;
                            in.push_back((P){X,Y});
                        }
                    }
                sta.push(in);
            }
            else{
                sscanf(&s[i],"%d",&val);
                in.clear();
                in.push_back(area[val]);
                tmp=area[val].x,area[val].x=area[val].y,area[val].y=tmp;
                in.push_back(area[val]);
                sta.push(in);
            }
        }
    }
    in=sta.top();
    for(i=0;i<in.size();i++)
        if(in[i].x*in[i].y<ans)
            ans=in[i].x*in[i].y;
    printf("%d\n",ans);
}