571B. Minimization(Codeforces Round #317)
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.
3 2
1 2 4
1
5 2
3 -5 3 -5 3
0
6 3
4 3 4 3 2 5
3
In the first test one of the optimal permutations is 1 4 2.
In the second test the initial order is optimal.
In the third test one of the optimal permutations is 2 3 4 4 3 5.
解题思路:
将数组分成k组,各自是i,i+k,i+2*k,i+3*k...(1<=i<=k),有x=n%k个组元素个数是n/k+1个,问题就转化为k组内
相邻元素差值的和的最小值,这时就须要对数组进行排序。仅仅有每组内的元素都是有序的,每组内的相邻元素的
差值才会最小,接着就是在k组内分x组长度为n/k+1,这时就须要dp,dp[i][j]。i是分了i组。j组长度是n/k+1;dp方
程为dp[i][j]=max(dp[i-1][j]+dp[i-1][j-1])+(a[i*n/k+j+1]-a[i*n/k+j]),ans=a[n]-a[1]-dp[k][x],a[i*n/k+j+1]-a[i*n/k+j]是要
从分第i组是,第i组的第1个元素与第i-1组的最后一个元素的差值。
代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=500000+100;
int a[maxn];
int s[maxn];
int bbs(int x)
{
if(x<0)
return -x;
return x;
}
int dp[5500][5500];
int main()
{
int n,k;
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
sort(a+1,a+n+1);
memset(dp,-1,sizeof(dp));
int sum=a[n]-a[1];
int q=n/k;
int x=n%k;
dp[0][0]=0;
for(int i=1;i<=k;i++)
{
for(int j=0;j<=x;j++)
{
int df;
if(j==0)
df=dp[i-1][j];
else
df=max(dp[i-1][j],dp[i-1][j-1]);
if(df<0)
continue;
if(i==k&&j==x)
dp[i][j]=df;
else
dp[i][j]=df+a[i*q+j+1]-a[i*q+j];
}
}
int ans=sum-dp[k][x];
cout<<ans<<endl;
return 0;
}
最新文章
- Android 升级SQLite数据库
- 【POJ2778】DNA Sequence(AC自动机,DP)
- 新版Chrome自动禁用第三方插件的解决办法[转]
- jenkins2 javahelloworld
- Mybaits学习总结2
- SGU 130
- Mysql数据库导入命令Source详解
- 【转】C#.net拖拽实现获得文件路径
- Python中AND-OR的用法
- oracle 之 内存—鞭辟近里(一)
- 【初码干货】记一次分布式B站爬虫任务系统的完整设计和实施
- 【LeetCode】258. Add Digits
- Spring系列__01HelloWorld
- Linux进程管理 (9)实时调度类分析,以及FIFO和RR对比实验
- RabbitMQ 安装与使用
- (华中科大)江南雨烟 C++ STL 专栏
- logging日志模块,hashlib hash算法相关的库,
- 51.从首页内容跳转到第二个Tabbar控制器(controller)
- css框架,一把锋利的剑
- 【LeetCode】230. Kth Smallest Element in a BST (2 solutions)