不同组合是34种

转载自:YxMadOSの部屋的博客
【分析】

说实在的，这是我在省选题目里见到的最水的题没有之一！

我们知道，连续2的i次幂可以组成任何不大于2^(i+1)的正整数。。于是这个题就出来了。。

把所有的m分成两种情况：

一开始不断用2的次幂相加，直到相加后不超过m的最大值。设k为m-2^i

1>剩余的k不为2的次幂，那么直接把k作为单独的一组即可。

证明：我们需要构成[1,m]的所有价格，当需要构成的价格price<=m-k的时候，用之前的2的次幂金钱数的钱袋就可以完成；需要构成价格price>m-k时，可以转化为求构成price-k价格的可行解，因为price-k<m-k，又可以转化为前一种price<m-k的情况，证毕。

2>剩余的k恰好是2的次幂，那么需要把k+1作为一组，将上一个2的次幂-1构成一组。

证明：当需要构成的价格price<=m-k-1的时候，可以很明显地看出m-k-1是属于1>的情况，按1>的方案可解决；当需要构成的价格price>m-k-1的时候，可以转化为求构成price-k-1价格的可行解，因为price-k-1<=m-k-1，又转化为了前一种情况，证毕。

#include"stdio.h"
int main()
{

 long m,s[100000],t=0;

 scanf("%ld",&m);

 while(m>0)

 {
  if(m%2==0)
   s[t++]=m/2;
  else
   s[t++]=m/2+1;
  m-=s[t-1];

 }

 printf("%ld\n",t);

 for(int i=t-1;i>=0;i--)
  printf("%ld ",s[i]);
  getchar();
  getchar();
}

可支付任意数的钱所装的金币满足数列1 2 4 7 12 20 从第三项等于前两项之和加1，
int f(int n)
{
    if（n>2)
       return f(n-1)+f(n-2)+1;
    else return n
}

我晕！不合题意吧

差不多 呵呵!

带的金币总数M=数列的和，n就所带的钱袋数

[问题描述] 设有已知面额的邮票m种，每种有n张。用总数不超过n张的邮票进行组合，能组合的邮票面额中可以连续出现面额数最多有多少？(1<=m<=100,1<=n<=100,1<=邮票面额<=255) 输第一行：n和m的值，中入:间用一空格隔开。第二行：a[1..m](面额) ，每个数中间用一空格隔开。输出:连续面额数的最大值

题解自己看吧是pascal的
http://hi.baidu.com/lzh070707/blog/item/c4eff1c67ff0eda38326acdd
也可以搜 NOIP1999 邮票面值设计