poj1017
Packets
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 29616 | Accepted: 9757 |
Description
A factory produces products packed in square packets of the same height h and of the sizes 1*1, 2*2, 3*3, 4*4, 5*5, 6*6. These products are always delivered to customers in the square parcels of the same height h as the products have and of the size 6*6. Because of the expenses it is the interest of the factory as well as of the customer to minimize the number of parcels necessary to deliver the ordered products from the factory to the customer. A good program solving the problem of finding the minimal number of parcels necessary to deliver the given products according to an order would save a lot of money. You are asked to make such a program.
Input
The input file consists of several lines specifying orders. Each line specifies one order. Orders are described by six integers separated by one space representing successively the number of packets of individual size from the smallest size 1*1 to the biggest size 6*6. The end of the input file is indicated by the line containing six zeros.
Output
The output file contains one line for each line in the input file. This line contains the minimal number of parcels into which the order from the corresponding line of the input file can be packed. There is no line in the output file corresponding to the last ``null'' line of the input file.
Sample Input
0 0 4 0 0 1 7 5 1 0 0 0 0 0 0 0 0 0
Sample Output
2 1
这题过得比较舒服，写得比较蛋疼，我感觉几周以后看自己的代码都看不懂。。。所以，写个题解纪念下。。。
思路是贪心。
6*6的格子，可以放下：1个6*6 or 1个5*5+11个1*1 or 1个4*4+5个2*2
由于边长4 5 6的只能填进一个洞，直接加上就是了，然后空隙尽量填满，大的优先（最大的只有2，1总能填到2里）
剩下只有边长3的，两种情况：4个3*3 和 不足4个3*3的（-_-b）
算一下可以发现，能把4个3*3分开装 和 先装4个3*3再装别的 比，效果是一样的。。。于是就先按4个3*3的方式塞满。。。
剩下1？2？3？ 个3*3的。。。算一下（-_-b）也能得出，放一块的效果不必放一起差。。。
然后。。。就没有然后了。。。2和1，照算可也
附自己看不懂的代码：
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#define dill do{if(s[2]<0)s[1]-=4*(-s[2]);if(s[1]<0)s[1]=0;if(s[2]<0)s[2]=0;}while(0)
int
main ( int argc, char *argv[] )
{
int s[7],i,sum=0,t[3][2]={{1,5},{3,6},{5,7}};
for(;;)
{
sum=0;
for(i=1;i<=6;i++){scanf("%d",&s[i]);sum+=s[i];}
if(sum==0)break;
sum=0;
sum+=s[6]+s[5]+s[4]+s[3]/4;
s[1]-=11*s[5];
s[2]-=5*s[4];
dill;
s[3]%=4;
if(s[3]){
s[2]-=t[3-s[3]][0];
s[1]-=t[3-s[3]][1];
sum++;
dill;
}
sum+=s[2]/9;
s[2]%=9;
if(s[2]){
s[1]-=36-s[2]*4;
sum++;
}
if(s[1]>0)sum+=s[1]/36+(s[1]%36>0?1:0);
printf("%d\n",sum);
}
return EXIT_SUCCESS;
}
poj1015
求其啦～是但啦～20101219
在标题上打个日期。。。有点多余～
不知道为什么，心血来潮，想写点东西。。
但真正要写了，又不知道写什么。。
本来今天自习了一天，挺满足的。。。
晚上，疯子问我有限域的内容，不会，感觉那个下午白看了～
最怕这种感觉，似懂，又非懂，尤其在数学上～
挺喜欢数学的，有机会重来的话，说不定就学数学了。。。
但现在，一学期三门数学，讲得飞快。。。
完全为考试而学的样子，不求甚解。。。
很怀念印象中那种属于数学的感觉，很奇妙～
可惜，被糟蹋了。。。
想起两部电影，香港拍的，觉得不错。。。
童梦奇缘，还有麦兜故事。。。
在我看来，不错，就是让人回味。。。
总试图参透出当初没看到的内涵～
那些谁都知道的道理～
到了这个年纪，想的就多了～
发情期，好像大家都这样。。。