跳至正文

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; }

发表评论

您的电子邮箱地址不会被公开。