IntelligentWarehouse

NC211807. IntelligentWarehouse

描述

In MI Intelligent Warehouse, there are $n_{}$ products, where the $i_{}$ -th product is of size $a_i$ . We always need to box producsts into all kinds of containers, and it will be safer and more cost efficient if for any two sizes of products, one is the other's multiple, since there won't be any residual room in one container. So for each boxing we need to choose some products that for any two chosen products, either $a_i$ is multiple of $a_j$ or $a_j$ is multiple of $a_i$ . Print the maximum number of products that can be chosen in one boxing.

输入描述

The first line contains one integer .

The second line contains  integers .

输出描述

Only one line containing one integer, denoting the maximum number of products we can choose in one boxing.

示例1

输入:

6
1 4 2 8 5 7

输出:

说明:

One possible choice is {1, 4, 2, 8}.

原站题解

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

C++ 解法, 执行用时: 937ms, 内存消耗: 78724K, 提交时间: 2021-09-15 17:22:03

#include<bits/stdc++.h>
using namespace std;
const int N=1e7;
int cnt[N+5],dp[N+5];
int main(){
	int n,num,ans=0;
	cin>>n;
	for(int i=1;i<=n;i++){
		scanf("%d",&num);
		cnt[num]++; 
	}
	for(int i=1;i<=N;i++)
		if(cnt[i]){
			dp[i]+=cnt[i];
			for(int j=i*2;j<=N;j+=i)
				dp[j]=max(dp[i],dp[j]);
			ans=max(ans,dp[i]);
		}
	cout<<ans;
	return 0;
}

上一题

下一题

详情