8597?石子劃分問題
時間限制:500MS? 內存限制:1000K
提交次數:155 通過次數:53
題型: 編程題???語言: G++;GCC;VC
?
Description
給定n個石子，其重量分別為a1,a2,a3,...,an。 要求將其劃分為m份，每一份的劃分費用定義為這份石子中最大重量與最小重量差的平方。 總劃分費用為m份劃分費用之和。現在對于給定的n個石子，求一種劃分方案，使得總劃分費用最小。
輸入格式
第一行兩個正整數n和m，接下來一行有n個正整數，表示一個石子的重量ai。(1≤n, m, ai≤1000)
輸出格式
計算輸出最小總劃分費用。注意：若一份只有一個石子，那么，這份石子中最大重量與最小重量的差的平方為0。
?
輸入樣例
4 2 4 7 10 1
?
輸出樣例
18
?
提示
1,先將石子重量從小到大排序(從大到小也可以).
2,假設f(n,m)表示:n個石頭分成m份的最小費用. 特別的,有f(1,1)=0; f(n,1)=(an - a1)^2
那么,除去最后一份石頭的若干個,前面m-1份必定也是最優的分法.
若最后一堆1個石頭, f(n,m) = f(n-1,m-1)+0^2
若最后一堆2個石頭, f(n,m) = f(n-2,m-1)+(an - an-1)^2
若最后一堆3個石頭, f(n,m) = f(n-3,m-1)+(an - an-2)^2
......
最后一堆最多只能有n-m+1個石頭,因為當最后一堆為n-m+1時,前面m-1堆已經是一個一份了.
因此, f(n,m) = Min{ f(n-1,m-1)+0^2, f(n-2,m-1)+(an - an-1)^2, ...}例如:
n=5, m=2
a[1..5] = 1 3 4 8 9
f(5,2)=Min{ f(4,1)+0; f(3,1)+1; f(2,1)+5^2 }=Min{49,10,29}=10
這5個石頭分2堆的最優分法：（1 3 4）（8 9） ?
這題需要記錄，做的時候居然又忘記了。
首先貪心，排序后，相鄰的排在一堆是必然的。
?
然后每次只考慮最后一堆即可是吧，其他的遞歸處理。
所以，設dp[i][j]表示前i個數字，分成j堆的最小值。
那么，考慮最后一堆，肯定是min(dp[1...i-1][j-1]? ?+? ?pow(a[n] - a[n - i + 1], 2));
?
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL;#include <iostream> #include <sstream> const int maxn = 1e3 + 20; int dp[maxn][maxn]; int a[maxn]; int dfs(int n, int m) {if (m == 1) return (a[n] - a[1]) * (a[n] - a[1]);if (n == m) return 0;if (dp[n][m]) return dp[n][m];int ans = 1e9;for (int i = 1; i <= n - m + 1; ++i) {ans = min(ans, dfs(n - i, m - 1) + (a[n] - a[n - i + 1]) * (a[n] - a[n - i + 1]));}return dp[n][m] = ans; }void work() {int n, m;cin >> n >> m;for (int i = 1; i <= n; ++i) cin >> a[i];sort(a + 1, a + 1 + n);cout << dfs(n, m) << endl; }int main() { #ifdef localfreopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endifwork();return 0; }
?
?
?
作者
?zhengchan
