Description
如果你有足够的石块，那么建一座金字塔绝不算难事。举个例子，在一块平地上，我们铺一个10*10的矩形，然后在10*10的矩形上面铺一个9*9的，然后8*8的……以此类推，直到顶上1*1。这个金字塔有10层，我们称这类金字塔为“高金字塔”。
如果你认为这样的金字塔太陡了，那么我们有办法让他看上去坡度平缓一些。比如，在10*10的矩形上，我们铺一个8*8的矩形，然后是6*6的……这样的金字塔只有5层了，大约为底座边长的一半。我们称之为“矮金字塔”。
很久以前，一位法老从父亲那儿继承了一大堆用于搭建金字塔的石块。他决定用这些石块搭建一座金字塔——每个石块都必须用上。建筑师告诉他，这样的要求不一定能实现。例如，如果你有10块石头，那么可以搭一个底座为3的矮金字塔；如果有5块石头，那么就搭一个底座为2的高金字塔。如果你有7块石头呢？不幸的是，确实找不出一种搭金字塔的方案了。
思考再三后，法老决定放低要求——搭不止一座金字塔。但是仍然要满足如下几个条件：
1.所有石块都必须用上；
2.金字塔数要尽可能少；
3.所有金字塔两两不同；
4.金字塔至少包含两层，即底座为1的金字塔和底座为2的矮金字塔是不允许的；
5.满足以上4点的基础上，最大的金字塔要尽可能大（大定义为用的石块数多）；
6.满足以上5点的基础上，次大的金字塔要尽可能大；
7.以此类推。。
你能求出最好的搭金字塔方案么？或者告诉法老这是做不到的。
金字塔只有300多种，先做一次bitset优化的0-1背包（保证条件1.3.4.），然后对每个询问搜索出条件2.的最优解（处理出哪些n可以用1到3个拼出，其余则只能>=4，用于最优性剪枝），通过搜索顺序保证条件5.6.7.
#include<cstdio>
#include<algorithm>
#include<bitset>
int s1[],s2[];
struct item{
int v,a,t;
bool operator<(item x)const{return v!=x.v?v<x.v:t<x.t;}
}is[],ps[],ps1[];
std::bitset<>f[];
int ip=,pp,mf[];
void dfs(int n,int w,int t){
if(t+mf[n]>=pp)return;
if(!n){
pp=t;
for(int i=;i<t;++i)ps[i]=ps1[i];
}
if(!w)return;
if(n>=is[w].v&&f[w-].test(n-is[w].v))ps1[t]=is[w],dfs(n-is[w].v,w-,t+);
dfs(n,w-,t);
}
int main(){
s1[]=s2[]=;
for(int i=;i<=;++i){
s1[i]=s1[i-]+i*i;
s2[i]=s2[i-]+i*i;
}
for(int i=;s1[i]<=;++i)is[++ip]=(item){s1[i],i,};
for(int i=;s2[i]<=;++i)is[++ip]=(item){s2[i],i,};
std::sort(is+,is+ip+);
f[].set();
for(int i=;i<=ip;++i)f[i]=f[i-]|f[i-]<<is[i].v;
for(int i=;i<=ip;++i){
int x=is[i].v;
if(!mf[x])mf[x]=;
}
for(int i=;i<=ip;++i){
for(int j=i+;j<=ip;++j){
int x=is[i].v+is[j].v;
if(x<=&&!mf[x])mf[x]=;
}
}
for(int i=;i<=ip;++i){
for(int j=i+;j<=ip;++j){
for(int k=j+;k<=ip;++k){
int x=is[i].v+is[j].v+is[k].v;
if(x<=&&!mf[x])mf[x]=;
}
}
}
for(int i=;i<=;++i)if(!mf[i])mf[i]=;
for(int _t=,n;;++_t){
if(scanf("%d",&n)!=||!n)return ;
if(!f[ip].test(n))printf("Case %d: impossible\n",_t);
else{
printf("Case %d:",_t);
pp=;
dfs(n,ip,);
for(int i=;i<pp;++i)printf(" %d%c",ps[i].a,"LH"[ps[i].t]);
puts("");
}
}
}