POJ 1837 Balance dp

https://vjudge.net/problem/POJ-1837
题目大意：$n$n个砝码，$m$m个挂钩，给出$m$m个挂钩的位置，范围在$[-15,15]$[−15,15]，负数表示在天平左侧，正数表示在天平右侧。然后给出$n$n个砝码的重量，问在使用全部砝码的前提下使得天平平衡的方案数。

思路：$dp[i][j]$dp[i][j]表示在使用了$i$i个砝码达到状态$j$j时的方案数。考虑到天平一侧的重量最多为$20*25*15=7500$20∗25∗15=7500，而且负数下标不好处理，我们搞一个$dp[n+1][15005]$dp[n+1][15005]的数组，并初始化$dp[0][7500]=1$dp[0][7500]=1。然后逐个考虑砝码：第$i$i个砝码可以放到任意一个挂钩上，于是有：$dp[i][j+w_i*m_j]+=dp[i-1][j]$dp[i][j+wi​∗mj​]+=dp[i−1][j]可以剪枝去掉一些没有意义的情况。最终答案就是$dp[n][7500]。$dp[n][7500]。

#include<cstdio>
#define INF 0x3f3f3f3f
#define eps 1e-8
#define pr pair<int,int>
using namespace std;
typedef long long ll;

int dp[25][15005];
int v[25],w[25];

int main()
{
    int n,m;
    scanf("%d%d",&m,&n);
    for(int i=1;i<=m;i++)
        scanf("%d",&v[i]);
    for(int i=1;i<=n;i++)
        scanf("%d",&w[i]);
    dp[0][7500]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=15000;j++)
        {
            if(dp[i-1][j])//只考虑有效的状态
            {
                for(int k=1;k<=m;k++)
                    dp[i][j+w[i]*v[k]]+=dp[i-1][j];
            }
        }
    }
    printf("%d\n",dp[n][7500]);
    return 0;
}