学步园

参照了 http://blog.sina.com.cn/s/blog_617615cd0100ewej.html

题目大意：给一个天平的悬挂点的坐标，和一些砝码，要你全部把砝码挂上去，保证天平平衡，一共有多少种方案

解题思路，动态规划，转换成0,1背包问题，用dp[i][j]表示前i个砝码都挂上，平衡度为j的方案数

dp[i][j + hooks[k] * weight[i]] += dp[i-1][j]，hooks[k]表示第k个悬挂点的坐标，weight[i]表示第i个砝码的重量

由于平衡度会有负数的情况出现，所以我们要选取一个点作为0参考点，保证平衡度不会出现负数

选取力矩最小的绝对值作为0坐标参考点，即|hooks[i] * sum(weight[k])|，也就意味着0坐标点平移到这个坐标

最好dp[G][min]为所求，min = |hooks[i] * sum(weight[k])|

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int maxn = 15 * 20 * 25 + 1;

int dp[21][maxn], hooks[21], weight[21], C, G;
int main()
{
    int tot = 0;
    memset(dp, 0, sizeof(dp));
    scanf("%d %d", &C, &G);
    for(int i = 1; i <= C; i++)
        scanf("%d", &hooks[i]);
    for(int i = 1; i <= G; i++)
    {
        scanf("%d", &weight[i]);
        tot += weight[i];
    }
    int minv = tot * hooks[1], maxv = tot * hooks[C];
    int gap = maxv - minv;
    dp[0][-minv] = 1;
    for(int i = 1; i <= G; i++)
    {
        for(int j = 0; j <= gap; j++)
        {
            if(dp[i-1][j] > 0)
            {
                for(int k = 1; k <= C; k++)
                    dp[i][j+weight[i] * hooks[k]] += dp[i-1][j];
            }
        }
    }
    printf("%d\n", dp[G][-minv]);
    return 0;
}