[HNOI2006]鬼谷子的钱袋

真的是神奇的解法呢

笔者最开始想到的是二进制拆分，然而发现最后的余数可能也是个2的幂，于是想到把余数拆一个1出来。但这样做并不能最小化钱袋个数。

怎么凑N？先分一个(frac{N}{2})出来，然后凑剩下的一半！

比如凑21，就这么凑

1. 21=11+10
2. 10=5+5
3. 5=3+2
4. 2=1+1

所以21=11+5+3+1+1

为什么这样是最优的呢？因为没有比这更优的。

我们知道，数字越小拆分的部分越少。而每次拆(frac{N}{2})是极限，不能再小了。不然(frac{N}{k}+1sim N-frac{N}{K}-1)的部分就凑不出来了。综上，这就是解法的神奇证明。显然就是在瞎扯淡

#include<cstdio>
#include<algorithm>
using namespace std;
int m;
int a[100],la;
void calc(int x){
    a[++la]=x-x/2;
    if(x==1)return;
    calc(x/2);
}
int main(){
    scanf("%d",&m);
    calc(m);
    printf("%d
",la);
    for(int i=la;i>=1;i--)printf("%d ",a[i]);
    return 0;
}