题目大意:给你6种大理石,每种大理石i的个数为num[i],价值为i,问你有没有策略能时它分成两份,两份总价值相等。
解题思路:0/1多重背包问题。
dp[i][j] = max{dp[i - 1][j - k * i] + k * i} 这里的i为第i种大理石的价值, 0<=k<= num[i], dp[i][j] 表示选择前i种大理石,总价值不超过j时的最大价值总和。最后验证dp[n][mid] 是否等于mid , mid = sum(i * num[i]) / 2;
多重背包,根据拆分思想,把每种大理石num[i]拆分成2进制表示。然后转换成为0/1背包问题。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; int const maxn = 300010; int num[7], value[maxn], tot; int dp[maxn]; void split(int n, int v); int main() { int n = 1; while(true) { memset(dp, 0, sizeof(dp)); int val = 0; for(int i = 1; i <= 6; i++) { scanf("%d", &num[i]); val += i * num[i]; } if(val == 0) break; printf("Collection #%d:\n", n++); if((val & 1) != 0) { printf("Can't be divided.\n\n"); continue; } tot = 0; for(int i = 1; i <= 6; i++) split(num[i], i); int mid = val >> 1; for(int i = 0; i < tot; i++) { for(int j = mid; j >= value[i]; j--) dp[j] = max(dp[j], dp[j - value[i]] + value[i]); } if(dp[mid] == mid) printf("Can be divided.\n\n"); else printf("Can't be divided.\n\n"); } return 0; } void split(int n, int v) { int index = 0, x, tmp = 0; while(n > 0) { x = 1 << index; if(tmp + x > n) break; tmp += x; value[tot++] = x * v; index++; } x = n - tmp; if(x > 0) value[tot++] = x * v; }
另一种方法为单调队列的方法,复杂度为O(VN)
具体的解释方法见这个链接,这里有详细解释,不做阐述
http://blog.csdn.net/flyinghearts/article/details/5898183
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; struct node { int index, value; }; int const maxn = 300010; int num[7], value[maxn], index[maxn], tot; node que[maxn]; int dp[maxn]; void split(int n, int v); int main() { int n = 1; while(true) { memset(dp, 0, sizeof(dp)); int val = 0; for(int i = 1; i <= 6; i++) { scanf("%d", &num[i]); val += i * num[i]; } if(val == 0) break; printf("Collection #%d:\n", n++); if((val & 1) != 0) { printf("Can't be divided.\n\n"); continue; } int mid = val >> 1; for(int i = 1; i <= 6; i++) { int t = i * num[i]; if(num[i] == 1) { for(int j = mid; j >= i; j--) dp[j] = max(dp[j], dp[j - i] + i); } else if(t >= mid) { for(int j = i; j <= mid; j++) dp[j] = max(dp[j], dp[j - i] + i); } else { for(int j = 0; j < i; j++) { int head = 0, tail = -1; for(int k = j, nu = 0; k <= mid; k += i, nu++) { if(head <= tail) { if(k - que[head].index > t) head++; } int tt = dp[k] - nu * i; while(head <= tail && que[tail].value < tt) tail--; tail++; que[tail].index = k; que[tail].value = tt; dp[k] = que[head].value + nu * i; } } } } if(dp[mid] == mid) printf("Can be divided.\n\n"); else printf("Can't be divided.\n\n"); } return 0; }