poj 1837 Balance

题意：求平衡状态， c个位置，g个物体重量，求有多少种平衡状态。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 
 6 int main()
 7 {
 8     int c,g,d[25][15000],h[25],w[25];//d 的第一个代表物品个数，第二个代表现在的平衡状态，>7500为向右偏
 9     cin>>c>>g;
10     for(int i=1; i<=c; i++)
11     cin>>h[i];
12     for(int i=1; i<=g; i++)
13     cin>>w[i];
14     memset(d,0,sizeof(d));
15 
16     for(int i=1; i<=c; i++)
17     d[1][h[i]*w[1]+7500]++;//加第一个物体，加7500为了消去负数
18     
19     for(int i=2; i<=g; i++)//第二到g个；
20     {
21         for(int j=0; j<=15000; j++)
22         if(d[i-1][j]==0)
23         continue;
24         else
25         for(int k=1; k<=c; k++)
26         d[i][j+w[i]*h[k]]+=d[i-1][j]; //状态转移方
27     }
28     cout<<d[g][7500]<<endl;//g个物体，7500为平衡状态
29     return 0;
30 }