公布一下上次出的那道题的参考答案(VC6.0,没有考虑输入格式)：
基本思路是用递归。
原题
http://keyfc.net/bbs/disp.asp?titleid=12274&page=3#include <stdio.h>
#include <memory.h>
#include <algorithm>
#define MAXINT 32767
#define MAX_CRACKERS 200
#define MAX_BOXES 10
int cache[MAX_CRACKERS+1][MAX_CRACKERS+1][MAX_BOXES+1];
using std::_cpp_min;
using std::_cpp_max;
/** @brief 计算函数
* @param start [in] 已知当Mailbox里的爆竹少于start个时，Mailbox不会炸坏
* @param end [in] MailBox无法装入多于end个爆竹，或者已知装入多于end个爆竹会炸毁
* @param boxes [in] 剩余可用的Mailbox个数
* @return 最坏情况下最少需要的爆竹数
*/
int getmin(const int start,const int end,const int boxes)
{
if(start>end) // 不需要试验
return 0;
if(start==end) // 只需要用start=end个爆竹试验一次
return start;
if(cache[start][end][boxes]==-1)
{
int s=MAXINT;
if(boxes==1) // 只有一个Mailbox，只能逐一增加
{
s=0;
for(int i=start; i<=end; i++) s+=i;
}
else
{
for(int i=start; i<=end; i++) // 在Mailbox中放置i个爆竹
{
s=_cpp_min(s, i+ //加上已经用去的i个爆竹
_cpp_max( //取两种情况所需爆竹数的较大值
getmin(start,i-1,boxes-1), //如果炸毁，boxes减少1，递归计算
getmin(i+1,end,boxes) //如果没有炸毁，boxes不变，递归计算
) );
}
}
cache[start][end][boxes]=s;
}
return cache[start][end][boxes];
}
/** @brief 主函数 */
int main(int argc, char* argv[])
{
int k,m;
memset(cache,-1,sizeof(cache)); //初始化递归缓存
printf("k(boxes)=");
scanf("%d",&k);
printf("m(max firecracks)=");
scanf("%d",&m);
printf("%d\n",getmin(1,m,k)); //计算
return 0;
}
