链接：https://codeforces.com/problemset/problem/571/B
思路：又是自己想了个假贪心想了半天，事实上贪心如果很难想到能满足方法的时候应该就是个dp题了，我们考虑其实可以看成k条链，并且每条连上一定放的是排序后的连续的一段，那么问题转化为了排序后序列划分为k条链，每条的长度必须为n / k或者n / k + 1，那么用dp[i][j]表示选了i个n / k的链，选了j个n / k + 1的链，然后每次代价为链上最后一个数 - 第一个数，更新即可。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
using namespace std;
int n, k;
int sz;
const int maxn = 3e5 + 5;
int a[maxn];
typedef long long ll;
ll dp[5005][5005];
int (){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> k;
int x1 = k - n % k, x2 = n % k;
for(int i = 0; i <= x1; i++){
for(int j = 0; j <= x2; j++){
dp[i][j] = 1e18;
}
}
for(int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + n + 1);
dp[0][0] = 0;
for(int i = 0; i <= x1; i++){
for(int j = 0; j <= x2; j++){
if(i < x1) dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + a[(i + 1) * (n / k) + j * (n / k + 1)] - a[i * (n / k) + j * (n / k + 1) + 1]);
if(j < x2) dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + a[i * (n / k) + (j + 1) * (n / k + 1)] - a[i * (n / k) + j * (n / k + 1) + 1]);
}
}
cout << dp[x1][x2] << 'n';
return 0;
}
|
近期评论