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 }