有大神可以提示一下，這題有甚麼特殊情況須注意嗎?
感覺測資怪怪的 :(   

有大神可以提示一下，這題有甚麼特殊情況須注意嗎?
感覺測資怪怪的 :(   

令 $dp[i]$ 是把前 $i$ 袋分群後被收走的錢最少是多少，枚舉轉移點 $j$，如果 $j+1\sim i$ 這段區間錢的總和 $\text{sum}\leq m$，可以讓 $dp[i]=\min(dp[i],dp[j] + (m-\text{sum})^2)$，因為 $m$ 最大到 $100$，每袋錢袋的錢 $\geq 1$，所以每個 $dp[i]$ 最多只有 $100$ 個轉移點，複雜度 $O(nm)$，最後只要比較所有錢總和與 $dp[n]$ 的大小就好了。

有大神可以提示一下，這題有甚麼特殊情況須注意嗎?
感覺測資怪怪的 :(   

令 $dp[i]$ 是把前 $i$ 袋分群後被收走的錢最少是多少，枚舉轉移點 $j$，如果 $j+1\sim i$ 這段區間錢的總和 $\text{sum}\leq m$，可以讓 $dp[i]=\min(dp[i],dp[j] + (m-\text{sum})^2)$，因為 $m$ 最大到 $100$，每袋錢袋的錢 $\geq 1$，所以每個 $dp[i]$ 最多只有 $100$ 個轉移點，複雜度 $O(nm)$，最後只要比較所有錢總和與 $dp[n]$ 的大小就好了。

becaidorz

有大神可以提示一下，這題有甚麼特殊情況須注意嗎?
感覺測資怪怪的 :(   

令 $dp[i]$ 是把前 $i$ 袋分群後被收走的錢最少是多少，枚舉轉移點 $j$，如果 $j+1\sim i$ 這段區間錢的總和 $\text{sum}\leq m$，可以讓 $dp[i]=\min(dp[i],dp[j] + (m-\text{sum})^2)$，因為 $m$ 最大到 $100$，每袋錢袋的錢 $\geq 1$，所以每個 $dp[i]$ 最多只有 $100$ 個轉移點，複雜度 $O(nm)$，最後只要比較所有錢總和與 $dp[n]$ 的大小就好了。

becaidorz

終於弄懂了, 此題是可以兩個以上的錢袋相互合併的
感謝！