UVa 311

题目大意:

有1*1,2*2,3*3,4*4,5*5,6*6大小的盒子,要把它们装到6*6的盒子里,它们的高度都是相同的。求用最少的6*6盒子把所有尺寸的盒子都装起来。

分析:(参考 D_Double's Journey的博客)

6*6的盒子中可以由各种尺寸的盒子来填满。可以有以下这些情况:

1个6*6

1个5*5+11个1*1

1个4*4+5个2*2(有空隙时优先放置2*2,如果没放完2*2的,剩下的就放置1*1) 

放置3*3时,组合情况比较复杂。 没有放完3*3时,剩下的空隙也是优先尽可能多地放置2*2 当放置1个3*3时,还可以放置7个1*1和5个2*2 当放置2个3*3时,还可以放置6个1*1和3个2*2 当放置3个3*3时,还可以放置5个1*1和1个2*2

因为一个4*4,5*5,6*6只能放置在一个盒子里,所以有多少个这些,就需要多少个盒子来装。

然后因为3*3的可以和1*1和2*2的组合放置,所以也可以确定装完3*3需要的盒子。

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 int main()
 5 {
 6     int n,a,b,c,d,e,f,x,y;
 7     int m[4]={0,5,3,1};
 8     while(1)
 9     {
10         scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&e,&f);
11         if(a==0&&b==0&&c==0&&d==0&&e==0&&f==0)
12             break;
13         n=d+e+f+(c+3)/4;
14         y=5*d+m[c%4];
15         if(b>y)
16             n+=(b-y+8)/9;
17         x=36*n-36*f-25*e-16*d-9*c-4*b;
18         if(a>x)
19             n+=(a-x+35)/36;
20         printf("%d
",n);
21     }
22     return 0;
23 }
原文地址:https://www.cnblogs.com/sunshinemxh/p/4792866.html