首页 > 移动平台 > 详细

【题解】移动牛棚

时间:2018-10-23 17:12:39      阅读:151      评论:0      收藏:0      [点我收藏+]

这个题刚看上去我整个人都是懵的,但是真的仔细研究一下的话,还是能看出其中的线索的,建议现在对这道题一头雾水的同学先思考一下,再回来看题解(读题的坑好大啊QAQ)

那么线索是什么呢

  1. d的算式暗藏玄机,这不是一个普普通通的值,而是第1头牛在1上,第n头牛在s上时的相邻牛之间的距离

     也就是说,第一头牛必须在1上,第n头牛必须在s上

   2.相邻2头牛之间的距离要么是d(没误差),要么是d+1(有误差),这就是所谓的相邻牛距离与d之差不超过1

   3.因为有了上一条,所以我们必须有且只能有s-(n-1)*d个误差间隔

   4.因为第i-1个牛棚只可能是相隔d或d+1,所以有f[i][j]=min(f[i-1][j],f[i-1][j-1])+abs(a[i]-(i-1)*d-j),f[i][j]是前i个点中有j个误差间隔时的最优答案

读题到这里就大概有个思路了吧,接下来只要随意dp,再滚一维数组就可以了

上代码吧

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,s,d;
int a[1502],f[1502];
int main()
{
    scanf("%d %d",&n,&s);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    d=(s-1)/(n-1);
    sort(a+1,a+n+1);
    memset(f,633,sizeof(f));
    f[1]=a[1]-1;//边界,第一头牛离它本应在的位置1的距离
    for(int i=2;i<=n;i++)
    {
        for(int j=min(i,s-(n-1)*d);j>=1;j--)
      //倒着算,滚掉一维,因为我们用到的是f[i-1][j-1]和f[i-1][j],还要取个min,因为一共i个点,不能大于i,最多只需s-(n-1)*d个误差间隔 { f[j]=min(f[j-1],f[j])+abs(a[i]-(i-1)*d-j);//别忘加上当前牛离目标的距离 } } printf("%d",f[s-(n-1)*d]); }

结束

【题解】移动牛棚

原文:https://www.cnblogs.com/xiaojuA/p/9837544.html

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