Codeforces Round #317 (Div. 2) D Minimization (贪心+dp)
2 seconds
256 megabytes
standard input
standard output
You've got array A, consisting of n integers and a positive integer k. Array A is indexed by integers from 1 to n.
You need to permute the array elements so that value
became minimal possible. In particular, it is allowed not to change order of elements at all.
The first line contains two integers n, k (2 ≤ n ≤ 3·105, 1 ≤ k ≤ min(5000, n - 1)).
The second line contains n integers A[1], A[2], ..., A[n] ( - 109 ≤ A[i] ≤ 109), separate by spaces — elements of the array A.
Print the minimum possible value of the sum described in the statement.
You've got array A, consisting of n integers and a positive integer k. Array A is indexed by integers from 1 to n.
You need to permute the array elements so that value
became minimal possible. In particular, it is allowed not to change order of elements at all.
The first line contains two integers n, k (2 ≤ n ≤ 3·105, 1 ≤ k ≤ min(5000, n - 1)).
The second line contains n integers A[1], A[2], ..., A[n] ( - 109 ≤ A[i] ≤ 109), separate by spaces — elements of the array A.
Print the minimum possible value of the sum described in the statement.
按照下标取模后的值可以分成k组,对于一组来说,按照升序排相邻的差之和是最小的,可用交换法证明,不难看出,总和等于a[end]-a[start]。对于不同的两组,
公共元素一定在端点,同样交换法可证,因此将整个数组排序以后相同一组一定连续。有n%k个长度为n/k+1的,其他的长度为n/k。
因此需要决策长度的选法,定义dp[i][j]表示选了i个长度为n/k+1,j个长度为n/k的组的最小花费。那么决策是下一个区间是长或者是短,边界条件dp[0][0] = 0表示什么也不选的时候花费为0。dp[i][j] = min(dp[i-1][j]+cost(i-1,j,L),dp[i][j-1]+cost(i,j-1,S))。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 3e5+, maxk = ;
int a[maxn];
int dp[][maxk];
int n,k,len; int cost(int i,int j,int L)
{
int s = (i+j)*len+i, e = s+len+L-;
return a[e]-a[s];
} int main()
{
//freopen("in.txt","r",stdin);
scanf("%d%d",&n,&k);
for(int i = ; i < n; i++) scanf("%d",a+i);
sort(a,a+n);
int tot = k, r = n%k;
int L = r, S = tot-r;
len = n/k;
for(int i = ; i <= L; i++){
int cur = i&, pre = cur^;
for(int j = ; j <= S; j++){
if(i && j) dp[cur][j] = min(dp[pre][j]+cost(i-,j,),dp[cur][j-]+cost(i,j-,));
else if(i) dp[cur][j] = dp[pre][j]+cost(i-,j,);
else if(j) dp[cur][j] = dp[cur][j-]+cost(i,j-,);
else dp[cur][j] = ;
}
}
printf("%d",dp[L&][S]);
return ;
}
最新文章
- W3School-CSS 字体(font)实例
- 从程序员到CTO的Java技术路线图
- SQL存储过程大全
- 为什么上传文件的表单里要加个属性enctype
- linux下挂在u盘,移动硬盘的方法,转移服务器资料的时候,使用移动硬盘什么最方便了
- Jersey(1.19.1) - Client API, Uniform Interface Constraint
- Ajax结合Js操作灵活操作表格
- Dynamics CRM 权限整理二
- 第十六次 ccf 201903-2 二十四点
- 使用powerpoint的表对象
- Oracle数据库---用户与角色
- C#——WebApi 接口参数传参详解
- 【深入Struts2】获取ServletAPI的三种方式
- Java 与 Json的互相转换
- Rails: could not connect to database postgres: FATAL: Peer authentication failed for user ";username";
- 查看修改MySQL字符集
- rabbitmq使用日记
- 会话控制(session和cookie)、跨页面传值
- Web Sessions Installation
- php和mySQL结合使用