POJ 1837 Balance dp

https://vjudge.net/problem/POJ-1837

題目大意： n n n個砝碼， m m m個挂鈎，給出 m m m個挂鈎的位置，範圍在 [ − 15 , 15 ] [-15,15] [−15,15]，負數表示在天平左側，正數表示在天平右側。然後給出 n n n個砝碼的重量，問在使用全部砝碼的前提下使得天平平衡的方案數。

思路： d p [ i ] [ j ] dp[i][j] dp[i][j]表示在使用了 i i i個砝碼達到狀态 j j j時的方案數。考慮到天平一側的重量最多為 20 ∗ 25 ∗ 15 = 7500 20*25*15=7500 20∗25∗15=7500，而且負數下标不好處理，我們搞一個 d p [ n + 1 ] [ 15005 ] dp[n+1][15005] dp[n+1][15005]的數組，并初始化 d p [ 0 ] [ 7500 ] = 1 dp[0][7500]=1 dp[0][7500]=1。然後逐個考慮砝碼：第 i i i個砝碼可以放到任意一個挂鈎上，于是有： d p [ i ] [ j + w i ∗ m j ] + = d p [ i − 1 ] [ j ] dp[i][j+w_i*m_j]+=dp[i-1][j] dp[i][j+wi​∗mj​]+=dp[i−1][j]可以剪枝去掉一些沒有意義的情況。最終答案就是 d p [ n ] [ 7500 ] 。 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;
}