题目描述

奶牛手上有 N 枚硬币，第 i 枚硬币的面值是 d[i] 元。无人售货机有 1000 件礼物，编号从 1 至 1000 ，第件礼物需要 i 元，售货机不设找赎。奶牛想知道：对于第 i 件礼物，有多少种凑币方案可以凑出 i 元？

输入格式

第一行，一个整数 N 。1<=N<= 40。

第二行，N 个整数，第 i 个整数是 d[i] 。1 <= d[i] <= 100。

输出格式

一行，共 1000 个整数，第 i 个整数表示凑出 i 元的方案数。

样例

4
2 3 4 5

0 1 1 1 2 1 2 1 2 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ......0

完善程序

#include<bits/stdc++.h>
using namespace std;
int n;
int a[105];
long long dp[1005]; 
int main()
{
	cin >> n;
	for(int i = 0; i < n; i++)
		cin >> a[i];
	
	__填空(1)__ = 1;
	for (int i=0;i<n;i++) 
		for (int j=1000;__填空(2)__;j--) 
			dp[j] += __填空(3)__;
	
	for(int i=1;i<=1000;i++) 
		cout << dp[i] << ' ';
	
	return 0;
}

填空(1):{{ input(1) }}

填空(2):{{ input(2) }}

填空(3):{{ input(3) }}