自动搬运

查看原文

来自洛谷，原作者为

	ezоixx130 这个家伙很懒，什么也没有留下

搬运于2025-08-24 21:42:15，当前版本为作者最后更新于2017-09-09 07:49:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这道题目是一道动规的题目。

令f[i][j]代表到了第i个检查点，跳过了j个的最短距离。

那么很容易写出转移方程：

f[i][j]=min(f[i-l-1][j-l]+dis(i,i-l-1))

（其实很暴力）

时间复杂度：O(n^3)但是常数很小。

代码：

#include <bits/stdc++.h>
using namespace std;

int n,k,x[501],y[501],f[501][501],a[501][501];

inline int dis(int a,int b){
    return abs(x[a]-x[b])+abs(y[a]-y[b]);
}

int main()
{
    memset(f,0x7f,sizeof(f));
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;++i)
    {
        scanf("%d%d",&x[i],&y[i]);
    }
    f[1][0]=0;
    for(int i=0;i<=n;++i)
        f[i][i]=0;
    for(int i=2;i<=n;++i)
        for(int j=0;j<=min(i-1,k);++j)
            for(int l=0;l<=j;++l)f[i][j]=min(f[i][j],f[i-l-1][j-l]+dis(i,i-l-1));
    printf("%d\n",f[n][k]);
}