Balance（poj 1837）

题意：一个天平上有C个挂钩，第i个挂钩的位置为C[i]，C[i] < 0表示该挂钩在原点的左边，C[i] > 0表示该挂钩在原点的右边；然后给出G个钩码的重量，问有多少种挂法使得天平保持平衡。

/*

      首先定义一个平衡度j的概念：当平衡度j=0时，说明天枰达到平衡，

  j>0，说明天枰倾向右边（x轴右半轴），j<0则相反

      f[i][j]表示钩码挂到第i个时，平衡度为j的方案数

      由于距离c[i]的范围是-15~15，钩码重量的范围是1~25，钩码数量

  最大是20，因此最极端的平衡度是所有物体都挂在最远端，因此平衡度

  最大值为j=15*20*25=7500。原则上就应该有f[ 1~20 ][-7500 ~ 7500 ]。

  因此为了不让下标出现负数，数组开为f[1~20][0~15000]，则当j=7500时

  天枰为平衡状态

      当我们挂到第i个时，面临一个抉择：向哪里挂？摆在我们眼前的是

  C个挂钩码的位置，我们应该每个钩码都挂一次试试，假设挂到第k个位置

  时，当前平衡值为j，挂完这个钩码后，j变成j+pos[k]*w[i],因此我们得

  到转移方程：f[i][j]+=f[i-1][j+pos[k]*w[i]]

*/

#include<cstdio>

#include<iostream>

#define M 10010

#define N 25

using namespace std;

int w[N],pos[N],f[N][M],C,G;

int main()

{

    scanf("%d%d",&C,&G);

    for(int i=;i<=C;i++)

      scanf("%d",&pos[i]);

    for(int i=;i<=G;i++)

      scanf("%d",&w[i]);

    f[][]=;

    for(int i=;i<=G;i++)

      for(int j=;j<=;j++)

          for(int k=;k<=C;k++)

          if(j+pos[k]*w[i]>=)

            f[i][j]+=f[i-][j+pos[k]*w[i]];

    printf("%d",f[G][]);

    return ;

}