2705 - 对抗赛
程序设计对抗赛疫有N（0<N<=50的整数）个价值互不相同的奖品，每个奖品的价值分别为S1，S2，S3......Sn(均为不超过100的正整数）。现将它们分给甲乙两队，为了使得甲乙两队得到相同价值的奖品，必须将这N个奖品分成总价值相等的两组。
编程要求：对给定N及N个奖品的价值，求出将这N个奖品分成价值相等级的两组，共有多少种分法？
例如：N=5，S1，S2，S3......Sn分别为1，5，3，8，9。则可分为{1，3，9}与{5，8}，仅有1种分法。
例如：N=7，S1，S2，S3.......Sn分别为1，2，3，4，5，6，7。
有4种分法：
{1，6，7}与{2，3，4，5}；
{2，5，7}与{1，3，4，6}；
{3，4，7}与{1，2，5，6}；
{1，2，4，7}与{3，5，6}；
题目输入
compepe.in
输入文件中包含N及S1，S2，S3......Sn。（每两个相邻的数据之间有一个空格隔开）。
题目输出
compepe.out
输出文件包含一个整数，表示多少种分法的答案，数据若无解，则输出0。
输入/输出样例
题目输入
7 1 2 3 4 5 6 7
题目输出
4
C语言解答
#include "stdio.h" int n,s; int a[50],f[50001]; int main() { int i,j; scanf("%d",&n); s=0; for(i=0;i<n;i++) { scanf("%d",&a[i]); s+=a[i]; } if(s%2) printf("0\n"); else { f[0]=1; s/=2; for(i=0;i<n;i++) { for(j=s;j>=a[i];j--) if(f[j-a[i]]) f[j]+=f[j-a[i]]; } printf("%d\n",f[s]/2); } return 0; }
C++解答
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int dp[51][3010], p[55]; int main() { // freopen("a.txt","r",stdin); int n, i, j, k; while(cin >> n) { memset(dp,0,sizeof(dp)); int sum(0); for(i = 1; i <= n; ++ i) { cin >> p[i]; sum += p[i]; } if(sum % 2) { cout << '0' << endl; continue; } dp[0][0] = 1; for(i = 1; i <= n; ++ i) { for(j = 0; j <= sum/2; ++ j) { dp[i][j] = dp[i-1][j]; if(j - p[i] >= 0) dp[i][j] = dp[i][j] + dp[i-1][j-p[i]]; } } cout << dp[n][sum/2]/2 << endl; } return 0; }