- 到現(xiàn)在為止，這道題我還是沒有完全理解，但是還是要把這個(gè)解題報(bào)告放出來，說不定寫著寫著我就明白了，說不定看著看著，我也就能明白了。
- 題意是給一個(gè)左右各長(zhǎng)15的桿子，在桿子的指定位置上掛C個(gè)掛鉤，給G個(gè)砝碼，不同重量，掛在桿子兩側(cè)，問何時(shí)達(dá)到平衡。
- 這道題的狀態(tài)我愣是沒確定了，被這道題嚇到了。平衡度，好吧，從來沒做過類似的DP題。
這道題的最終結(jié)果還是求助得來的，天，又是求助……只求做一道會(huì)一道吧。
狀態(tài)dp[i][j]表示當(dāng)用了前i個(gè)物品，平衡度為j的掛法的數(shù)量，題里面要求的應(yīng)該是求所有g(shù)個(gè)物品掛上去以后，平衡度為0的掛法吧，好吧，暫時(shí)先不管它，極端情況就是所有的物品都掛在最遠(yuǎn)端，那極端情況就應(yīng)該是25*20*15=7500，按照題意，應(yīng)該就是左邊7500，右邊7500，范圍應(yīng)該是[-7500..7500]，移植到C語言里面就是[1..15000]，所求的就是dp[g][7500]。
如果第i個(gè)物品掛在某一個(gè)掛鉤上，一定在掛上前i-1個(gè)物品的所產(chǎn)生的某平衡度的基礎(chǔ)上產(chǎn)生了一個(gè)新的平衡度，不同的掛鉤平衡度不同，第i個(gè)物品掛在每一個(gè)掛鉤上面所產(chǎn)生的新平衡度的掛法都要加上前i-1個(gè)物品所產(chǎn)生的舊平衡度的掛法，方程有點(diǎn)兒麻煩，先不列了，放在下面的代碼中好了……
特別鳴謝：翔哥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