|
|
思路：
力矩 = 力臂*重量。這個高中物理學過啦，呵呵。
所以如果現在有一個 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;
}
|