题目描述

奶牛手上有 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

1. 问题:若干硬币任意组合后，能表示哪些面值？

结论: 以每个硬币为阶段。

2.状态: dp[i][j] 表示用第 i 个硬币组合时，能否表示面值 j ;

3.状态转移方程:

dp[i][i]=dp[i-1][i] //不用第i个硬币

dp[i][i]=1 (i>=a[i] &&dp[i-1][j-a[i]==1) //用第i个硬币(1<=i<=n ，0<=i<=1000)

4.问题的解:

{ dp[n][j]==0}

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

完成程序

#include<bits/stdc++.h>
using namespace std;
int dp[105][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=0;j<=1000;j++)
		{
			dp[i][j]=dp[i-1][j];
			if(j>=a[i]&&__填空(2)__)  dp[i][j]=1;
		}
	}

	for(int j=0;j<=1000;j++)
		if ( __填空(3)__ )
            cout<<j<<' ';

	return 0;
}

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

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

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