卖箱人

NC201629. 卖箱人

描述

你是一个卖箱子的人，每天顾客都会要求买不同容量的箱子，允许你拿这n种箱子去组成顾客所要求的容量，由于你是个大老板，有个巨大的仓库，所以可以认为每一种箱子都有无限个。

现在摆在你面前有n种箱子，每种箱子的容量为ai。现在问你有多少个容量你组合不出来。若有无限个，则输出INF.

输入描述

第一行一个整数n
第二行n个整数,

输出描述

输出无法组成出来的容量的个数，若有无限个，请输出INF

示例1

输入:

2
4 5

输出:

说明:

只有1, 2, 3, 6, 7, 11这6个数凑不出来

示例2

输入:

2
4 6

输出:

INF

说明:

所有的奇数都无法被凑出来,所以是无限个

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++ 解法, 执行用时: 5ms, 内存消耗: 592K, 提交时间: 2022-04-02 21:20:32

#include<bits/stdc++.h>
using namespace std;
int a[100000],dp[100000];
map<int,int>kl;
int c[100000],n;
int N=5e4+10;
int main()
{

	//首先有1绝对INF
	//没1绝对不INF 
	cin>>n;
	int ans=0,x;
	dp[0]=1;
for(int i=1;i<=n;i++)
{
	cin>>x;
	for(int j=x;j<=N-1;j++)
	{
		dp[j]+=dp[j-x];
	}
}
for(int i=1;i<=N-1;i++)
{
	if(!dp[i])
	ans++;
}
if(ans>=2500)
cout<<"INF";
else
cout<<ans;
	
}

上一题

下一题

详情