Balance

 1 #include <stdio.h>
 2 #include <string.h>
 3 const int N=15002;
 4 int dp[21][N];
 5 int main()
 6 {
 7     int n,num;
 8     int dis[21],w[21];
 9     memset(dp,0,sizeof(dp));
10     scanf("%d%d",&n,&num);// n钩子数，num砝码数
11     for (int i = 1; i <= n; i ++)
12         scanf("%d",&dis[i]);
13     for (int j = 1; j <= num; j ++)
14         scanf("%d",&w[j]);
15     dp[0][7500] = 1;//砝码数为0达到平衡的方法有一种
16     for (int i = 1; i <= num; i ++)
17     {
18         for (int j = 0; j <= 15000; j ++)
19         {
20             if (dp[i-1][j])
21             {
22                 for (int k  = 1; k <= n; k ++)
23                 {
24                     //状态转移方程
25                     dp[i][j+dis[k]*w[i]] += dp[i-1][j];
26                 }
27             }
28         }
29     }
30     printf("%d
",dp[num][7500]);
31     return 0;
32 }
View Code