USACO 2.2.2 Subset Sums 解题报告

这一题是一个动态规划题，f[i][j]是i个数字（1, 2, 3, 4, .., i）能够组成和为i的个数，那么方程式是f[i][j] = {f[i – 1][j – k] + f[i – 1][j]} (1 <= k <= i)，再DP就是的，代码如下： / LANG: C ID: yylogoo1 PROG: subset / #include long long f[781]; int main(void) { int n, i, j, k; int max = 0; freopen("subset.in", "r", stdin); freopen("subset.out", "w", stdout); scanf("%d", &n); if(((n + 1) n / 2) & 1){ printf("0\n"); return 0; } f[0] = 1; for(i = 1; i = i; j--){ f[j] += f[j - i]; } } printf("%ld\n", f[(n + 1) n / 4] / 2); return 0; }