#include <iostream> #include <cstdio> #include <algorithm> #include <string> using namespace std; //有20件物品,可知即使用递归,时间复杂度为2^n,计算量在1000000左右,不会超时 int a[21]; int mem[21][41];//状态表示数组 //求拿商品方法总数,m种商品,容积capacity int ways(int m, int capacity) //实际上就是状态计算 { if (capacity < 0) //当容积小于0,方法数自然为0 return 0; if (capacity == 0) { mem[m][capacity] = 1;//当容积为0时,方法数自然为1 return 1; } if (m == 0 && capacity != 0) { mem[m][capacity] = 0;//此时方法数亦为0 return 0; } if (mem[m][capacity] != -1) { return mem[m][capacity];//mem[m][capacity]非初始值-1时,存储的正是对应的方法数 } else { //递推关系的由来:首先状态表示数组mem[m][capacity]的含义是-- //在最多选m件物品的前提下,总体积为capacity的方法数 //故可以推出下列递推式 //接着来看上文各种特殊情况的判定 // mem[m][capacity] = ways(m - 1, capacity) + ways(m - 1, capacity - a[m]); return mem[m][capacity]; } } int main() { int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; } for (int i = 0; i < 21; i++) { for (int j = 0; j < 41; j++) { mem[i][j] = -1;//刷新状态数组 } } cout << ways(n, 40) << endl; return 0; } // 64 位输出请用 printf("%lld")