题面
题意: 要用尽量少的6*6的箱子放入一些1*1~6*6的物品, 设他们分别有$latex a_i$个.
首先答案至少要$latex a_6+a_5+a_4$这么多, 因为他们是不能多个并存的. 然后对于5*5和4*4的物品我们就可以贪心地在空隙中插入物品. 对于放了5*5的箱子每个可以插11个1*1. 对于放了4*4的箱子每个可以放5个3*3和7个1*1, 如果放不满就尽可能放1*1. 最后考虑3*3的, 尽量每4个放满一个箱子, 然后讨论剩余1, 2, 3个4*4时能插入多少个1*1和2*2. 最后剩下的1*1和2*2随便放.
由于放每个物品时都尽可能利用所有的空间, 并且都排除了不可行解(不可能放多个的情况), 可以出全局最优. 思路简单, 细节多, 情况要考虑周全.
#include<cstdio>
#include<algorithm>
#define re register
#define in inline
#define int long long
using namespace std;
in int read()
{
int s(0),b(0);char ch;
do{ch=getchar();if(ch=='-')b=1;}while(ch<'0'||ch>'9');
while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
if(b)return -s;return s;
}
int a[7];
signed main()
{
while(1)
{
int ans=0,bb=0;
for(re int i=1;i<=6;++i) a[i]=read(),bb|=a[i];
if(!bb) break;
ans=a[6]+a[5]+a[4];
a[1]=a[1]-a[5]*11;
if(a[1]<0) a[1]=0;
a[2]=a[2]-a[4]*5;
if(a[2]<0&&a[1]) a[1]=a[1]+a[2]*4;
if(a[1]<0) a[1]=0;
if(a[2]<0) a[2]=0;
ans=ans+a[3]/4;
a[3]%=4;
if(a[3]) ++ans;
if(a[3]==1){
a[2]=a[2]-5;
if(a[2]<0&&a[1]) a[1]=a[1]+a[2]*4;
a[1]-=7;
if(a[1]<0) a[1]=0;
}
if(a[3]==2){
a[2]=a[2]-3;
if(a[2]<0&&a[1]) a[1]=a[1]+a[2]*4;
a[1]-=6;
if(a[1]<0) a[1]=0;
}
if(a[3]==3){
a[2]=a[2]-1;
if(a[2]<0&&a[1]) a[1]=a[1]+a[2]*4;
a[1]-=5;
if(a[1]<0) a[1]=0;
}
if(a[2]<0) a[2]=0;
if(a[2])
{
ans=ans+a[2]/9;
a[2]%=9;
if(a[2]) ++ans;
a[1]=a[1]-(36-a[2]*4);
if(a[1]<0) a[1]=0;
}
if(a[1])
{
ans=ans+a[1]/36;
a[1]%=36;
if(a[1]) ++ans;
}
printf("%lld\n",ans);
}
return 0;
}
CGaZn的博客
最新评论