zcmu-2137

2137: 和为T

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 66  Solved: 14
[Submit][Status][Web Board]

Description

从一个大小为n的整数集中选取一些元素，使得它们的和等于给定的值T。每个元素限选一次，不能一个都不选。

Input

　　第一行一个正整数n，表示整数集内元素的个数。
第二行n个整数，用空格隔开。
第三行一个整数T，表示要达到的和。

Output

　　输出有若干行，每行输出一组解，即所选取的数字，按照输入中的顺序排列。
若有多组解，优先输出不包含第n个整数的；若都包含或都不包含，优先输出不包含第n-1个整数的，依次类推。
最后一行输出总方案数。

Sample Input

5-7 -3 -2 5 90

Sample Output

-3 -2 5 -7 -2 9 2

HINT

1<=n<=22，T<=maxlongint

解析：根据题目要求，从前往后枚举，可以发现一个规律。

9	5	-2	-3	-7
0	0	0	0	1
0	0	0	1	0
0	0	0	1	1
0	0	1	0	0
0	0	1	1	0
0	0	1	1	1
0	1	0	0	0

这就是二进制枚举。但是这里却超时了。所以、换另外的一个写法，dfs。

dfs：

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<cctype> #include<cstdlib> #include<algorithm> #include<vector> #include<set> #include<map> #include<stack> #include<list> using namespace std; int v[22]; int q[22]; int n,ans,cnt=0; void result(int t) { if(t<0) { int sum=0,sumofv=0; for(int i=0;i<n;i++) { if(v[i]) sum+=q[i]; sumofv+=v[i]; } if(sum==ans&&sumofv) { for(int i=0;i<n;i++) if(v[i]) cout<<q[i]<<" "; cout<<endl; cnt++; } return; } for(int i=0;i<=1;i++) { v[t]=i; result(t-1); } } int main() { cin>>n; for(int i=0;i<n;i++) cin>>q[i]; cin>>ans; result(n-1); cout<<cnt<<endl; return 0; }

超时的二进制枚举法：

#include<bits/stdc++.h> using namespace std;typedef long ll;int main() {int n;ll t;ll a[200];while(~scanf("%d",&n)){int ans=0;for(int i=0; i<n; i++)scanf("%lld",&a[i]);scanf("%lld",&t);for(int i=1; i<(1<<n); i++){ll sum=0;for(int j=0; j<n; j++){if(i&(1<<j))sum+=a[j];}if(sum==t){for(int j=0; j<n; j++){if(i&(1<<j))printf("%lld ",a[j]);}puts("");ans++;}}printf("%d\n",ans);}return 0; }

总结

以上是生活随笔为你收集整理的zcmu-2137的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。