记录编号	159983	评测结果	AAAAAAAAAAAAAAA
题目名称	马拉松2	最终得分	100
用户昵称	Dijkstra	是否通过	通过
代码语言	C++	运行时间	0.624 s
提交时间	2015-04-23 15:26:19	内存使用	2.25 MiB

#include<fstream>
#include<cstring>
#include<cmath>
#define INF 0x7fffffff
#define LL long long
#include<algorithm>
#define MAXN 501
using namespace std;
ifstream fin("marathonb.in");
ofstream fout("marathonb.out");
struct point{LL x,y;};
int N,K;
LL d[MAXN],s[MAXN],F[MAXN][MAXN],ans=INF; 
point p[MAXN];
LL dis(point a,point b){return abs(a.x-b.x)+abs(a.y-b.y);}
int main()
{
	fin>>N>>K;
	for(int i=1;i<=N;i++) fin>>p[i].x>>p[i].y;
	memset(F,0x3F,sizeof(F));
	F[1][0]=0;
	for(int i=2;i<=N;i++)
		for(int j=0;j<i-1&&j<=K;j++)
			for(int k=i-1;k&&i-k-1<=j;k--)
				F[i][j]=min(F[i][j],F[k][j-(i-k-1)]+dis(p[i],p[k]));
	fout<<F[N][K]<<endl;
	return 0;
}