谷外题求调

题目描述小学合唱团有N名团员，依次编号为1...N。合唱团的每个团员都有一个唱歌音高，其中第i名团员的音高为H[i]，多名团员同时唱歌时，产生的音高是他们的音高之和。比如假设团员i的音高是5，团员j的音高是6，那么i和j一起唱歌时可以获得11的音高。如果某个团员X的音高可以通过其他团员一起唱歌得到，那么就可以不选择X。例如对于上面示例中的i和j，如果X的音高是11，那么X就可以不选择。最少需要选择多少名团员。

输入格式第1行：一个整数N，表示合唱团团员数量。（1 <= N <= 500）。

第2行：N个空格分隔的整数，其中第i个整数H[i]表示团员i的音高（1 <= H[i] <= 100000）。

输出格式输出共两行：

第1行：一个整数C，表示最少需要选择多少名团员。

第2行：C个空格分隔的整数，按照从小到大输出选出的C名团员的音高。

输入输出样例输入样例1： 3 5 6 11 输出样例1： 2 5 6 【耗时限制】1000ms 【内存限制】256MB

CPP

#include<bits/stdc++.h>
using namespace std;
int h[500+10],t[500+10];
bool d[100000+10];
int main (){
	int n,maxn=0,cnt=0;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>h[i];
		maxn=max(maxn,h[i]);
	}
	sort(h+1,h+n+1);
	d[0]=1;
	for(int i=1;i<=n;i++){
		if(d[h[i]]==1)continue;
		for(int j=maxn;j>=h[i];j--){
			d[j]+=d[j-h[i]];
		}
	}
	for(int i=1;i<=n;i++){
		if(d[h[i]]==0){
			t[++cnt]=h[i];
		}
	}
	cout<<cnt<<endl;
	for(int i=1;i<=cnt;i++){
		cout<<t[i]<<" ";
	}
 	return 0;
}

讨论操作

回复

相关推荐

谷外题求调