题目描述
LYK做了一个梦。
这个梦是这样的，LYK是一个财主，有一个仆人在为LYK打工。
不幸的是，又到了月末，到了给仆人发工资的时间。但这个仆人很奇怪，它可能想要至少x块钱，并且当LYK凑不出恰好x块钱时，它不会找零钱给LYK。
LYK知道这个x一定是1~n之间的正整数。当然抠门的LYK只想付给它的仆人恰好x块钱。但LYK只有若干的金币，每个金币都价值一定数量的钱（注意任意两枚金币所代表的钱一定是不同的，且这个钱的个数一定是正整数）。LYK想带最少的金币，使得对于任意x，都能恰好拼出这么多钱。并且LYK想知道有多少携带金币的方案总数。
具体可以看样例。
输入格式(dream.in)
第一行一个数n，如题意所示。
输出格式(dream.out)
输出两个数，第一个数表示LYK至少携带的金币个数，第二数表示方案总数。
输入样例
6
输出样例
3 2
样例解释
LYK需要至少带3枚金币，有两种方案，分别是{1,2,3}，{1,2,4}来恰好得到任意的1~n之间的x。
输入样例2
10
输出样例2
4 8
数据范围
对于30%的数据n<=10。
对于60%的数据n<=100。
对于100%的数据n<=1000。
分析：第一问很好处理，就是看n的二进制位上有多少个是1，第二问可以先考虑搜索，因为个数定了嘛，所以每次搜当前的和是多少，这一位数字从哪一个开始枚举，选了多少个数字，因为每个数字只能选一次，可以边递归边判断，方法和：传送门 差不多.
其实可以发现这就是一道dp嘛，把搜索时的参数变成状态就好了:f[i][j][k]表示前i个数字，和为j,最大的一个数字为k的方案数，递推非常好想，主要是空间问题，滚动数组优化一下就好了.
60分暴力：
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; int n, cnt, ans, f[21][1010][21]; void init(int x) { for (int i = 1; i <= x; i *= 2) { cnt++; x -= i; } if (x) cnt++; } int dfs(int dep, int sum, int l) { int cntt = 0; if (f[dep][sum][l]) return f[dep][sum][l]; if (dep == cnt + 1) { if (sum >= n) cntt++; return cntt; } for (int i = l; i <= sum + 1; i++) cntt += dfs(dep + 1, sum + i, i + 1); return f[dep][sum][l] = cntt; } int main() { scanf("%d", &n); init(n); printf("%d %d\n", cnt,dfs(1,0,1)); return 0; }
正解：
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; int n, cnt, f[2][1010][1010], last, now, ans; void init(int x) { for (int i = 1; i <= x; i *= 2) { cnt++; x -= i; } if (x) cnt++; } int main() { scanf("%d", &n); init(n); last = 0, now = 1; f[0][1][1] = 1; for (int i = 1; i < cnt; i++) { for (int j = 1; j <= n; j++) for (int k = 1; k <= n; k++) if (f[last][j][k]) for (int l = k + 1; l <= j + 1; l++) f[now][min(n, j + l)][l] += f[last][j][k]; swap(now, last); } for (int i = 1; i <= n; i++) ans += f[last][n][i]; printf("%d %d\n", cnt, ans); return 0; }
原文：http://www.cnblogs.com/zbtrs/p/7757829.html