【题解】移动牛棚

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

结束

【题解】移动牛棚

上一篇:【转】具透 | 你可能不知道,iOS 10 有一个中国「特供」的联网权限功能


下一篇:iOS浏览器 new Date() 返回 NaN