USACO 2.2 Subset Sums (DP動态規劃)

#include <stdio.h>
#define DEBUG 1
#define TESTCASES 9
#define MAX 39

//partitions[preNums][sum]表示在前preNums個數中選取，使總和為sum的方案數
//注意：第preNums個數,也就是最後一個數，可以選或者不選
//要long long 才不溢出
long long partitions[MAX + 1][800];
int n;

int main(){
#if DEBUG
	int testCase;
	for (testCase = 1; testCase <= TESTCASES; testCase++){
		char inputFileName[20] = "inputx.txt";
		inputFileName[5] = '1' +  (testCase - 1);
		freopen(inputFileName, "r", stdin);
		printf("\n#%d\n", testCase);
#endif

	scanf("%d", &n);

	int total = ((1 + n) * n) >> 1;
	if (total & 1){
		printf("0\n");
#if DEBUG
		continue;
#else
		return 0；
#endif
	}
	total = total >> 1;

	partitions[1][1] = 1;
	partitions[1][0] = 1;
	int max = 1;
	int preNums, sum;
	for (preNums = 2; preNums <= n; preNums++){
		int lastNum = preNums;
		max += lastNum;
		int limitSum = total > max ? total : max;
		for (sum = 0; sum <= limitSum ; sum++){
			if (sum < lastNum)
				partitions[preNums][sum] = partitions[preNums - 1][sum];
			else
				partitions[preNums][sum] = partitions[preNums - 1][sum] + partitions[preNums - 1][sum - lastNum];
		}
	}

	printf("%d\n", partitions[n][total] >> 1);

#if DEBUG
	}
#endif
	return 0;
}