codeforces 571B B. Minimization

2018-01-08 13:35:27来源:网络收集作者:程序诗人人点击

分享

阿里云爆款

        题意:给定一个长度为n的序列,请你变换它,使得Σ|a[i]-a[i+k]|最小,输出这个最小的Σ|a[i]-a[i+k]|。


        首先可以观察得到,对于一个i它之和i-k与i+k会发生关系,所以如果我们对所有的i,i+k,i+2*k从大到小排序之后,累加即可得到a[i]-a[i+k]+a[i+k]-a[i+2k]+a[i+2k]-a[i+3k]=a[i]-a[i+3k]。而又因为我们要想让差最小,所以a[i],a[i+k],a[i+2*k],必须放置为一串排序之后连续的数列,因为如果不连续的话,选连续的其中一个,肯定绝对值差更小。


        再进一步可以看出,每个和i相关的数字的长度只会有两种n/k+1与n/k,其数量分别为n%k(可以理解为分成k份之后多出来的)与k-n%k。由于k只有5000,我们不难用dp[i][j]来表示第一种长度考虑了i个了,第二种长度考虑了j个时最小的价值。而这个状态显而易见可以由dp[i-1][j](填第一种)与dp[i][j-1](填第二种)转移而来,而我们又有了第一段所推出来的式子,所以如果填第一种,那么填的这一段开头s就是(i-1)*len1+j*len2+1,结尾e就是s+len1-1了,所以我们就可以得到dp[i][j]=min(dp[i][j],dp[i-1][j]+a[e]-a[s])的方程了,选第二种同理可得。


        最后答案就是dp[n][m],注意啦,虽然答案有可能不会爆long long,但是如果dp开的是int,且memset的时候用0x3f做极大值大小是不够的,一种方法是手动memset,第二种方法是开long long,long long memset时候如果值为0x3f答案会更大。


       下附AC代码。


#include
#include
#include
#include
#define maxn 500005
using namespace std;
typedef long long ll;
int n,k;
ll a[maxn];
ll dp[5005][5005];
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
scanf("%I64d",&a[i]);
sort(a+1,a+1+n);
int len1=n/k+1,num1=n%k;
int len2=n/k,num2=k-n%k;
memset(dp,0x3f,sizeof(dp));
dp[0][0]=0;
for(int i=0;i<=num1;i++)
{
for(int j=0;j<=num2;j++)
{
if(i)
{
int s=(i-1)*len1+j*len2+1;
int e=s+len1-1;
dp[i][j]=min(dp[i][j],dp[i-1][j]+a[e]-a[s]);
}
if(j)
{
int s=i*len1+(j-1)*len2+1;
int e=s+len2-1;
dp[i][j]=min(dp[i][j],dp[i][j-1]+a[e]-a[s]);
}
}
}
printf("%I64d/n",dp[num1][num2]);
}

最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台