【51Nod】1510 最小化序列 贪心+动态规划

2018/05/24 07:33
阅读数 24

【题目】1510 最小化序列 【题意】给定长度为n的数组A和数字k,要求重排列数组从而最小化: ####$$ans=\sum_{i=1}^{n-k}|A_i-A_{i+k}|$$ 输出最小的ans,$n \leq 310^5,k \leq 5000,-10^9 \leq A_i \leq 10^9$。 【算法】贪心+动态规划 先对序列从小到大排序,通过贪心容易发现连续的段在一起时最优。所以实际上要求将序列分成$k$段,其中$n%k$个大段和其它小段,小段的段长是$g=\frac{n}{k}$,大段段长+1。 令$f_{i,j}$表示前面i个段有j个大段的最小代价,那么: ####$$f_{i,j}=min { f_{i-1,j-1}+a_{ig+j}-a_{(i-1)g+j},f_{i-1,j}+a_{ig+j}-a_{(i-1)*g+j+1} } $$ 复杂度$O(k^2+n \ \ log \ \ n)$。 注意:开long long会爆空间除非用滚动数组。不用ll的话必须用unsigned int否则中间过程会爆int。初始化f[0][0]=1,f[0][1~k]=inf非常重要。

#include<cstdio>
#include<cstring>
#include<algorithm>
bool isdigit(char c){return c>='0'&&c<='9';}
int read(){
	int s=0,t=1;char c;
	while(!isdigit(c=getchar()))if(c=='-')t=-1;
	do{s=s*10+c-'0';}while(isdigit(c=getchar()));
	return s*t;
}
using namespace std;
#define ll long long
const int maxn=300010,kind=5010;
int n,k,a[maxn],ans;
unsigned int f[2][kind];
int main(){
	n=read();k=read();
	for(int i=1;i<=n;i++)a[i]=read();
	sort(a+1,a+n+1);
	int g=n/k,num=n%k;
	int x=0;
	f[x][0]=0;for(int i=1;i<=k;i++)f[x][i]=2000000001;
	for(int i=1;i<=k;i++){
		x=1-x;
		f[x][0]=f[1-x][0]+a[i*g]-a[(i-1)*g+1];//long long
		for(int j=1;j<=k;j++)f[x][j]=min(f[1-x][j-1]+a[i*g+j]-a[(i-1)*g+j],f[1-x][j]+a[i*g+j]-a[(i-1)*g+j+1]);
	}
	printf("%d",f[x][num]);	
	return 0;
}
展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部