題目大意：

     給定一個形式的天枰，天枰上遠(yuǎn)離中點(diǎn)的不同距離擁有鉤子。給定各種重量砝碼，問必須懸掛所有砝碼的前提下，維持天枰平衡的掛法數(shù)為多少？

     暴力嘗試的枚舉量驚人，顯然即使天枰當(dāng)前不平衡，但它的“不平衡度”是可以利用的。關(guān)鍵是如何設(shè)計DP狀態(tài)。普遍的做法是以i個物品為階段，計算懸掛到第i個物品時，當(dāng)前平衡度達(dá)到v的方法總數(shù)。易得 -7500<=v<=7500； dp[i][v]=∑dp[i-1][v-hoox[j]*w[i]] → dp[i][v+inf]=∑dp[i-1][v-hoox[j]*w[i]+inf]。常數(shù) inf 僅為保證數(shù)組下標(biāo)不為負(fù)。我們明顯發(fā)現(xiàn)它在形式上類似于背包問題，等價于在v容背包中，嘗試放入重量為hoox[j]*w[i]的物品，換取收益一種方法。

     容易理解，初始解 dp[0][0+inf]=1，目標(biāo)解 dp[m][0+inf] 。

     類比:

       http://acm.ustc.edu.cn/ustcoj/problem.php?id=1116 

       DD牛 << 背包九講 >>

 1#include<cstdio>
 2#include<cstring>
 3#define G 21
 4#define N 21
 5#define inf 7500
 6
 7int dp[G][inf+inf+1];
 8int w[G],h[N];
 9
10int main(){
11    int n,m,i,j,v;
12    while(scanf("%d%d",&n,&m)!=EOF){
13        for(i=0;i<n;i++) scanf("%d",&h[i]);
14        for(i=1;i<=m;i++) scanf("%d",&w[i]);
15        
16        memset(dp,0,sizeof(dp));
17        dp[0][0+inf]=1;
18        
19        for(i=1;i<=m;i++)
20            for(v=-1*inf;v<=inf;v++)
21                for(j=0;j<n;j++)
22                    if( v-h[j]*w[i]+inf+1 )
23                        dp[i][v+inf]+=dp[i-1][v-h[j]*w[i]+inf];
24                    
25        printf("%d\n",dp[m][0+inf]);
26    }
27    return 0;
28}
29