题解 P2833 【[USACO14DEC]马拉松赛跑Marathon_Sliver】

· · 题解

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

令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]);
}