首页 > 代码库 > [USACO 2012 Jan Silver] Bale Share【DP】
[USACO 2012 Jan Silver] Bale Share【DP】
传送门：http://www.usaco.org/index.php?page=viewproblem2&cpid=107
没想到太不应该了，真的不应该啊！
f[i][j][k]表示前i个包，第一个包里共有j大小的物品，第二个包里共有k大小的物品是否成立，则方程为：
f[i][j][k] = f[i - 1][j - a[i]][k] || f[i - 1][j][k - a[i]] || f[i - 1][j][k];
观察方程，可以省去数组a改用单独一个变量，并使用滚动数组，详见代码。
#include <cstdio>const int maxn = 21;int n, a, s, ans = 2147483647;bool f[2005][2005];inline int minn(int aa, int ss) { return aa < ss? aa: ss;}inline int max3(int aa, int ss, int dd) { aa = aa > dd? aa: dd; return aa > ss? aa: ss;}int main(void) { freopen("baleshare.in", "r", stdin); freopen("baleshare.out", "w", stdout); scanf("%d", &n); f[0][0] = true; for (int i = 1; i <= n; ++i) { scanf("%d", &a); s += a; for (int j = s; j >= 0; --j) { for (int k = s - j; k >= 0; --k) { if (j >= a) { f[j][k] = f[j][k] || f[j - a][k]; } if (k >= a) { f[j][k] = f[j][k] || f[j][k - a]; } } } } for (int j = 0; j <= s; ++j) { for (int k = 0; j + k <= s; ++k) { if (f[j][k]) { ans = minn(ans, max3(j, k, s - j - k)); } } } printf("%d\n", ans); return 0;}
为什么会变成这样呢，明明是一道水题。。。
[USACO 2012 Jan Silver] Bale Share【DP】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。