poj_1837

4935 ワード

dp[i][j]前i個の分銅で、「モーメント」の大きさをjとした場合の数が極端な場合、20個の重量が25の分銅は、いずれも中心点-15からの位置に掛けられ、モーメントは-7500となるので、j=7500の場合はバランス状態とする
 1 #include <cstdio>

 2 #include <cstring>

 3 

 4 #define MAXN 20

 5 

 6 int C, G, dp[MAXN+1][2*MAXN*15*25+1], hook[MAXN+1], weight[MAXN+1];

 7 

 8 int main(int argc, char const *argv[])

 9 {

10     // freopen("in", "r", stdin);

11     scanf("%d%d", &C, &G);

12     for(int i = 1; i <= C; ++i)

13         scanf("%d", &hook[i]);

14     for(int i = 1; i <= G; ++i)

15         scanf("%d", &weight[i]);

16 

17     // initialize

18     memset(dp, 0 ,sizeof(dp));

19     dp[0][7500] = 1;

20 

21     // dp

22     for(int i = 1; i <= G; ++i)

23         for(int j = 0; j <= 15000; ++j)

24             if(dp[i-1][j])

25                 for(int k = 1; k <= C; ++k)

26                     dp[i][ j+hook[k]*weight[i] ] += dp[i-1][j];

27 

28     printf("%d
", dp[G][7500]); 29 return 0; 30 }