题目大意: 有一个天平，天平左右两边各有若干个钩子，总共有C个钩子(每个钩子有相对于中心的距离,左负右正)，有G个钩码，求将钩码全部挂到钩子上使天平平衡的方法的总数。
将每个砝码看作一组，组内各个物品的体积为每个挂钩与该砝码形成的力矩，背包总体积严格为0，这便是分组背包计数问题（特殊点：每一组必须出一个物品，而不是至多出一个物品）。由于c++不允许负的数组下标，所以每次更新时，j要加上offsetJ。
实现分组背包计数问题时，可以用填表法（找以前节点求自己值）（DP1）或刷表法（找以后节点更新以后值）（DP2）。由于刷表法时，如果DP[i][j]==0，可以跳过，所以节省时间。
注意：
- 不可以用一维数组倒序循环来表示DP数组，因为j-objV可能比j还大
- 同理，每次判断时，不是j-objV>=0，0代表天平的支点而不是左端点。所以应当为j-objV>=minJ。
#include#include #include using namespace std;const int MAX_V = 16000, MAX_OBJ = 30, MAX_HOOP = 30;const int Plus = 7500;#define Sub(x) x+offsetJint TotHoop;int Len[MAX_HOOP], W[MAX_OBJ];void _printf(char *format, ...){#ifdef _DEBUG va_list(args); va_start(args, format); vprintf(format, args); va_end(args);#endif}int DP1(int totHoop, int totDev, int *_w, int *_len){ int minJ = 0, maxJ = 0, wSum = 0, offsetJ, objV = 0; static int DP[MAX_OBJ][MAX_V]; for (int dev = 1; dev <= totDev; dev++) wSum += _w[dev]; for (int hoop = 1; hoop <= totHoop; hoop++) _len[hoop] > 0 ? maxJ += _len[hoop] * wSum : minJ += _len[hoop] * wSum; offsetJ = -minJ; DP[0][offsetJ] = 1; _printf("+ offsetJ %d maxJ %d\n", +offsetJ, maxJ); for (int i = 1; i <= totDev; i++) for (int j = minJ; j <= maxJ; j++) for (int hoop = 1; hoop <= totHoop; hoop++) { objV = _w[i] * _len[hoop]; if (j - objV >= minJ && j - objV <= maxJ) { DP[i][j + offsetJ] += DP[(i - 1)][j + offsetJ - objV]; _printf("%d=DP[%d][%d] += DP[%d][%d]=%d\n", DP[i][j + offsetJ], i, j, i - 1, j - _w[i] * _len[hoop], DP[i - 1][j - _w[i] * _len[hoop] + offsetJ]); } } return DP[totDev][offsetJ];}int DP2(int totHoop, int totDev, int *_w, int *_len){ int minJ = 0, maxJ = 0, wSum = 0, offsetJ, objV = 0; static int DP[MAX_OBJ][MAX_V]; for (int dev = 1; dev <= totDev; dev++) wSum += _w[dev]; for (int hoop = 1; hoop <= totHoop; hoop++) _len[hoop] > 0 ? maxJ += _len[hoop] * wSum : minJ += _len[hoop] * wSum; offsetJ = -minJ; DP[0][offsetJ] = 1; _printf("+ offsetJ %d maxJ %d\n", + offsetJ, maxJ); for (int i = 0; i < totDev; i++) for (int j = minJ; j <= maxJ; j++) if (DP[i][j+ offsetJ]) for (int hoop = 1; hoop <= totHoop; hoop++) { objV = _w[i+1] * _len[hoop]; DP[i + 1][j + objV + offsetJ] += DP[i][j + offsetJ]; _printf("%d=DP[%d][%d] += DP[%d][%d]=%d\n", DP[i+1][j+objV+ offsetJ], i+1, j+objV+ offsetJ, i, j+ offsetJ , DP[i][j + offsetJ]); } return DP[totDev][offsetJ];}int main(){#ifdef _DEBUG freopen("c:\\noi\\source\\input.txt", "r", stdin);#endif int totDevice, vCnt = 0, totV = 0, maxV = 0, minV = 0; scanf("%d%d", &TotHoop, &totDevice); for (int i = 1; i <= TotHoop; i++) scanf("%d", i + Len); for (int i = 1; i <= totDevice; i++) scanf("%d", i + W); printf("%d\n", DP2(TotHoop, totDevice, W, Len)); return 0;}