首页 > 其他 > 详细

P5017 摆渡车

时间:2019-08-26 21:41:17      阅读:103      评论:0      收藏:0      [点我收藏+]

技术分享图片

——————————————————————————————————————————————————-

想不到普及组的题都会这么有意思

数轴上转移,借鉴了@Sooke的剪枝思想,虽然就剪一个就A了

斜率优化在考虑中

——————————————————————————————————————

#include<bits/stdc++.h>
using namespace std;
int n,m,tt,a;
int cnt[4000100],sum[4000100],f[4000100];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++){cin>>a;tt=max(tt,a);cnt[a]++;sum[a]+=a;}
    for(int i=1;i<=tt+m;i++)cnt[i]+=cnt[i-1],sum[i]+=sum[i-1];
    for(int i=0;i<=tt+m;i++)
    {
        f[i]=cnt[i]*i-sum[i];
        for(int j=max(0,i-2*m+1);j<=i-m;j++)
        f[i]=min(f[i],f[j]+(cnt[i]-cnt[j])*i-sum[i]+sum[j]);    
    }
    int ans=0x3f3f3f3f;
    for(int i=tt;i<=tt+m;i++)ans=min(f[i],ans);
    cout<<ans;
}

 

P5017 摆渡车

原文:https://www.cnblogs.com/SFWR-YOU/p/11415151.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!