- 到現在為止,這道題我還是沒有完全理解,但是還是要把這個解題報告放出來,說不定寫著寫著我就明白了,說不定看著看著,我也就能明白了。
- 題意是給一個左右各長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
