题目描述

奶牛手上有 N 枚硬币，第 i 枚硬币的面值是 d[i] 元。无人售货机有 1000 件礼物，编号从 1 至 1000 ，第件礼物需要 i 元，售货机不设找赎。奶牛想知道：利用这枚硬币，哪些礼物是不可能买得到的?(如果奶牛无法凑出 i 元，即不可能买到第 1 件礼物;如果能凑出 i 元，那就有可能买第 i 件礼物)。从小到大输出不可能买得到的礼物的编号。

输入格式

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

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

输出格式

一行，从小到大输出不可能买得到的礼物的编号。

样例

3
2 3 6

1 4 7 10 12 13 14 ......1000

状态 dp[j] 记录是否存在能表示总面值为 j 的组合。

状态转移方程：

dp[j]=dp[j] //不用第i个硬币, 可省略

dp[j]=1 (j>=a[i] && dp[j-a[i]==1) //用第i个硬币

(1<=i<=n , 0<=j<=1000)

问题的解：

{ dp[j]==0 }

该算法的时间复杂度为 O(n*1000)。

完成程序

#include<bits/stdc++.h>
using namespace std;
int dp[1005];
int n,a[105];
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];

	__填空(1)__=1; //初始化

	for(int i=1;i<=n;i++)
		for(int j=1000;__填空(2)__;j--)
			if( __填空(3)__==1)  dp[j]=1;

	for(int j=0;j<=1000;j++)
		if ( dp[j]==0 )  cout<<j<<' ';
	
	return 0;
}

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

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

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