subset,USACO2.2.2 Subset Sums解题报告

Subset Sums JRM
For many sets of consecutive integers from 1 through N (1 <= N <= 39), _disibledevent=>

• {3} and {1,2}

This counts as a single partitioning (i.e., reversing the order counts as the same partitioning and thus does not increase the count of partitions).
If N=7, there are four ways to partition the set {1, 2, 3, ... 7} so that each partition has the same sum:

• {1,6,7} and {2,3,4,5}
• {2,5,7} and {1,3,4,6}
• {3,4,7} and {1,2,5,6}
• {1,2,4,7} and {3,5,6}

Given N, your program should print the number of ways a set containing the integers from 1 through N can be partitioned into two sets whose sums are identical. Print 0 if there are no such ways.
Your program must calculate the answer, not look it up from a table.

PROGRAM NAME: subset

INPUT FORMAT

The input file contains a single line with a single integer representing N, as above.

SAMPLE INPUT (file subset.in)

7

OUTPUT FORMAT

The output file contains a single line with a single integer that tells how many same-sum partitions can be made from the set {1, 2, ..., N}. The output file should contain 0 if there are no ways to make a same-sum partition.

SAMPLE OUTPUT (file subset.out)

4
题目大意就是求讲数据1…N分成两组，使得两组中元素的和加起来相等，求这样分组的情况数
可以利用递推的方法求该题的解，注意：f(k,a)=(f(k-1,a+k)+f(k-1,a-k))/2；其中f(k,a)表示讲1…k元素分两组，使第一组比第二组多a；
因为k只可能分到第一组或第二组这两种情况，如果k加到第一组后使得第一组比第二组多a，则要原来的分组中第一组比第二组多a-k
同理如果k加到第二组后使得第一组比第二组多a，则要原来的分组中第一组比第二组多a+k。
因为交换两组元素后也满足条件，而只算一个解，故后面要除2；
很显然题目要求的是f（N，0）；
为节省递推时间，可使用记忆化搜索，考虑到数据不大，又a有正负之分，可加数组适当开大。
1 /* 2 ID:shiryuw1 3 PROG:subset 4 LANG:C++ 5 */ 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 using namespace std; 13 int sum=0; 14 int n; 15 long long fid[40][2000]; 16 long long dp(int k,int a) 17 { 18 if(k==0) 19 { 20 return 0; 21 } 22 if(k==1) 23 { 24 if(abs(a)==1) 25 return 1; 26 return 0; 27 } 28 if(k==2) 29 { 30 if(abs(a)==1||abs(a)==3) 31 return 1; 32 return 0; 33 } 34 if(fid[k][a+1000]==-1) 35 fid[k][a+1000]=dp(k-1,a+k)+dp(k-1,a-k); 36 return fid[k][a+1000]; 37 } 38 39 int main() 40 { 41 freopen("subset.in","r",stdin); 42 freopen("subset.out","w",stdout); 43 cin>>n; 44 memset(fid,-1,sizeof(fid)); 45 printf("%lld\n",dp(n,0)/2); 46 return 0; 47 }

Tags:  subset

延伸阅读