|
|
思路：
力矩 = 力臂*重量。这个高中物理学过啦，呵呵。
所以如果现在有一个 3 放在 -5 的位置上，一个 4 放在 3 的位置上，那当前天平的总力矩就是 3*-5 + 4*3 = -3 了
动态规划：
从小到大依次放 weight。
f[i][j] = { 已经放了 i 个 weight，天平的总力矩为 j 时候的方案个数 }
初始化 f[0][0] = 1
状态转移：
对每个位置 x
f[i + 1][j + W[i + 1]*x] += f[i][j]
 #include <stdio.h>
#include <stdlib.h>
int C, G, X[24], W[24];
  struct  {
 int val, tm;
} _dp[2][1 << 15], *dp[2] = {
&_dp[0][_countof(_dp[0]) / 2],
&_dp[1][_countof(_dp[1]) / 2],
 }, *cur, *pre;
int up, down;
int main()
{
int i, j, k, y;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d%d", &C, &G);
for (i = 1; i <= C; i++)
scanf("%d", &X[i]);
for (i = 1; i <= G; i++)
scanf("%d", &W[i]);
dp[1][0].tm = 1;
dp[1][0].val = 1;
  for (i = 1; i <= G; i++) {
pre = dp[i & 1];
cur = dp[(i + 1) & 1];
for (j = down; j <= up; j++) {
if (pre[j].tm != i)
continue;
for (k = 1; k <= C; k++) {
y = j + W[i]*X[k];
if (cur[y].tm != i + 1) {
cur[y].tm = i + 1;
cur[y].val = 0;
 }
cur[y].val += pre[j].val;
if (y < down)
down = y;
if (y > up)
up = y;
}
}
}
printf("%d\n", cur[0].val);
return 0;
}
|