GZOI2011 Pack 解題報告

第一題（20分）

提交文件：Pack.exe

輸入文件：Pack.in

輸出文件：Pack.out

 
題目描述：

你在一個組合式傢俱廠工作，這種組合式傢俱由各種形狀不同的組件組成，例如：

图1 三种不同形状的组件

這些組件生產出來後將被自動裝箱，組件按生產的次序落下，第一個組件落在箱子底部，其後的組件依次落下，直至組件接觸到之前裝入的組件或箱子底部。例如，假設組件按圖1從左至右的次序生產出來，裝箱結果將如圖2左所示。假如按圖1從右至左的次序生產出來，裝箱結果將如圖2右所示。

                 圖2 不同的生產次序導致兩種不同的裝箱結果

由於箱子高度有限，如圖2左，三個組件已經超過了箱子的高度，這種情況第三個組件及之後的組件需要用新的箱子來裝。

你的工作是為自動裝箱系統編寫程序，根據組件生產的次序，輸出裝完這些組件後，每個箱子的組件堆疊的高度。

 

輸入格式（Pack.in）：

第一行是用空格分隔的三個整數n,w,b。n是一套傢俱的組件數，1<=n<=100，w和b是箱子的寬和高，1<=w<=10，1<=b<=100。接下來是n個組件的形狀描述，按生產的次序排列，每個組件描述第一行是一個整數h，1<=h<=10且h<=b，接下來h行每行w個字元，描述組件的形狀，“X”代表組件的部分，“.”代表空間。

輸出格式（Pack.out）：

m個整數（m代表裝箱所需的箱子數），按裝箱的次序輸出m個箱子裡組件的高度。

樣例

Pack.in	Pack.out
3 5 12 5 XXXXX .XXXX ..XXX ...XX ....X 4 XXX.. ..X.. ..XXX ..X.. 6 X.... X.... X.... X.... X.... XXXXX	9 6

【分析】
為什麼廣州的題都這樣？！看著很難，其實想想，還是模擬題！！
這題沒什麼好說的，模擬吧！

【我的代碼】
裸代碼

C++语言: Codee#25364

001 /*
002 *Problem: GZOI2011 Pack
003 *Author: Yee-fan Zhu
004 *Email: zyfworks@gmail.com
005 */
006 #include <cstdio>
007 #include <cstdlib>
008 #include <iostream>
009 using namespace std; 
010
011 int max(int a,int b)
012 {
013     return (a>b?a:b);
014 }
015
016 int N,W,H;/*
017     *N: The Number of the Furniture
018     *W:The Width of the Box
019     *H: The Height of the Box
020     */
021
022 class BOX
023 { 
024 public:
025     int top;
026     int Box[102][12];
027     BOX()
028     {
029         for (int i=0;i<=100;i++)
030             for (int j=0;j<=10;j++)
031                 Box[i][j]=0;
032     }
033 }B[101];
034 int now=1;
035
036 void Put(BOX Tmp)
037 {
038     if(B[now].top==0)
039     {
040         B[now]=Tmp;
041         return;
042     }
043     int tryit=B[now].top;
044     int tryme=1;
045     int res=0;
046     bool flag=true;
047     while(tryit>0 && tryme<=Tmp.top)
048     {
049         int tmp=B[now].top-tryme;
050         for (int i=1;i<=tryme;i++)
051         {
052             int k=tmp+i;
053             int freeposf[11]={0};
054             int freeposb[11]={0};
055             for (int j=1;j<=W;j++)
056             {
057                 freeposf[j]=Tmp.Box[i][j],
058                 freeposb[j]=!B[now].Box[k][j];
059                 if(freeposf[j]==1 && freeposb[j]==0)
060                 {
061                     flag=false;
062                     break;
063                 }
064             }
065             if(!flag)
066                     break;
067         }
068         if(!flag)
069             break;
070         tryit--;
071         tryme++;
072         res++;
073     }
074     int k=B[now].top-res+1;
075     if(Tmp.top+k-1>H)
076     { 
077         now++;
078         B[now]=Tmp;
079         return;
080     }
081    
082     for (int i=1;i<=Tmp.top;i++)
083     {
084         for (int j=1;j<=W;j++)
085             B[now].Box[k][j]=max(B[now].Box[k][j],Tmp.Box[i][j]);
086         k++;
087     }
088     B[now].top=k-1;
089 }
090
091 void init()
092 {
093     scanf("%d %d %d\n",&N,&W,&H);
094     int X;
095     BOX TmpBox;
096     char chr;
097     for (int k=1;k<=N;k++)
098     {
099         scanf("%d\n",&X);
100         for (int i=1;i<=X;i++)
101         {
102             for (int j=1;j<=W;j++)
103             {
104                 //scanf("%c",&chr);
105                 cin>>chr;
106                 if(chr=='X')
107                     TmpBox.Box[X-i+1][j]=1;
108                 if(chr=='.')
109                     TmpBox.Box[X-i+1][j]=0;
110             }
111         }
112         TmpBox.top=X;
113         Put(TmpBox);
114     }
115     for(int i=1;i<=now;i++)
116         printf("%d ",B[i].top);
117 }
118
119 int main()
120 {
121     freopen("pack.in","r",stdin);
122     freopen("pack.out","w",stdout);
123     init();
124     return 0;
125 }