总时间限制:
1000ms
内存限制:
65536kB
描述
一个工厂制造的产品形状都是长方体,它们的高度都是h,长和宽都相等,一共有六个型号,他们的长宽分别为1*1, 2*2, 3*3, 4*4, 5*5, 6*6。这些产品通常使用一个 6*6*h 的长方体包裹包装然后邮寄给客户。因为邮费很贵,所以工厂要想方设法的减小每个订单运送时的包裹数量。他们很需要有一个好的程序帮他们解决这个问题从而节省费用。现在这个程序由你来设计。
输入
输入文件包括几行,每一行代表一个订单。每个订单里的一行包括六个整数,中间用空格隔开,分别为1*1至6*6这六种产品的数量。输入文件将以6个0组成的一行结尾。
输出
除了输入的最后一行6个0以外,输入文件里每一行对应着输出文件的一行,每一行输出一个整数代表对应的订单所需的最小包裹数。
样例输入
0 0 4 0 0 1
7 5 1 0 0 0
0 0 0 0 0 0
样例输出
2
1
算法思想:
1.可见6*6,5*5,4*4,3*3都各需一个箱子
2.因为3*3箱子所搭配的箱子是不固定的,所以用个数组来保存不定情况
3.求剩余多少1*1箱子时,用整体减去已经存在的箱子最为简便
解决方案:
#include<iostream>
using namespace std ;
int main()
{
int a,b,c,d,e,f,i,sum;
int x,y ;
int p[4]={0,5,3,1};
cin>>a>>b>>c>>d>>e>>f ;
while(a||b||c||d||e||f)
{
sum = d+e+f+(c+3)/4 ; //3*3,4*4,5*5,6*6都可以确定需要的箱子
x = 5*d + p[c%4] ; //剩下能装多少个2*2
if(b>x) //2*2箱子多了
sum += ((b- x+8)/9);
y = 36*sum -f*36-25*e-16*d-9*c -4*b;//剩下能装多少个1*1
if(a>y)
sum += ((a-y+35)/36 );
cout<<sum<<endl ;
cin>>a>>b>>c>>d>>e>>f ;
}
return 0 ;
}
相关推荐
①找出最优解的性质,并刻画其结构特征 ②递归地定义最优值(写出动态规划方程) ③以自底向上的方式计算出最优值 ④根据计算最优值时记录的信息,构造最优解 ④,步骤
动态规划 1005 打导弹 1006 乘积最大 1007 加分二叉树 1008 合唱队形 1017 最大0,1子矩阵 这题要想不超时,必须DP 1020 最大正方形 这题和1017很相似,不过有更快的解决方法 1021 背包问题 1022 Longest ...
#POJ 题集 数论 欧几里得/拓展欧几里得算法 ...动态规划 背包 1014 高精度 加减乘除 1001 巧妙处理 思维处理 1852 模拟 1017 简单题 水题 1004 1007 1008 枚举 1013 预处理 1002 二分查找 1003 1005 ###贪心 1089
范例1-40 动态堆栈 90 ∷相关函数:push函数 Pop函数 1.3.10 动态队列 93 范例1-41 动态队列 93 ∷相关函数:Enqueue函数 1.3.11 初始化单循环链表 95 范例1-42 初始化单循环链表 95 ∷相关函数:ListLength...
范例1-40 动态堆栈 90 ∷相关函数:push函数 Pop函数 1.3.10 动态队列 93 范例1-41 动态队列 93 ∷相关函数:Enqueue函数 1.3.11 初始化单循环链表 95 范例1-42 初始化单循环链表 95 ∷相关函数:ListLength...
范例1-40 动态堆栈 90 ∷相关函数:push函数 Pop函数 1.3.10 动态队列 93 范例1-41 动态队列 93 ∷相关函数:Enqueue函数 1.3.11 初始化单循环链表 95 范例1-42 初始化单循环链表 95 ∷相关函数:ListLength_...