- 到现在为止，这道题我还是没有完全理解，但是还是要把这个解题报告放出来，说不定写着写着我就明白了，说不定看着看着，我也就能明白了。
- 题意是给一个左右各长15的杆子，在杆子的指定位置上挂C个挂钩，给G个砝码，不同重量，挂在杆子两侧，问何时达到平衡。
- 这道题的状态我愣是没确定了，被这道题吓到了。平衡度，好吧，从来没做过类似的DP题。
这道题的最终结果还是求助得来的，天，又是求助……只求做一道会一道吧。
状态dp[i][j]表示当用了前i个物品，平衡度为j的挂法的数量，题里面要求的应该是求所有g个物品挂上去以后，平衡度为0的挂法吧，好吧，暂时先不管它，极端情况就是所有的物品都挂在最远端，那极端情况就应该是25*20*15=7500，按照题意，应该就是左边7500，右边7500，范围应该是[-7500..7500]，移植到C语言里面就是[1..15000]，所求的就是dp[g][7500]。
如果第i个物品挂在某一个挂钩上，一定在挂上前i-1个物品的所产生的某平衡度的基础上产生了一个新的平衡度，不同的挂钩平衡度不同，第i个物品挂在每一个挂钩上面所产生的新平衡度的挂法都要加上前i-1个物品所产生的旧平衡度的挂法，方程有点儿麻烦，先不列了，放在下面的代码中好了……
特别鸣谢：翔哥zzxyyx_1
view code
1 #include <iostream>
2 #include <cstdio>
3 using namespace std;
4 int main()
5 {
6 int c, g, w[21], z[21], i, j, dp[21][15005], k;
7 cin >> c >> g;
8 for (i = 1; i <= c; i++) cin >> z[i];
9 for (i = 1; i <= g; i++) cin >> w[i];
10 dp[0][7500] = 1;
11 for (i = 1; i <= g; i++)
12 {
13 for (j = -7500; j <= 7500; j++)
14 {
15 if(dp[i - 1][j + 7500] != 0)
16 for (k = 1; k <= c; k++)
17 {
18 dp[i][j + z[k] * w[i] + 7500] += dp[i - 1][j + 7500];
19 }
20 }
21 }
22 cout << dp[g][7500] << endl;
23 return 0;
24 }
25