【悬赏1关注,1互关】求HACK
  • 板块UVA13288 Cordon Bleu
  • 楼主_H17_
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/11/26 18:01
  • 上次更新2023/11/26 20:17:45
查看原帖
【悬赏1关注,1互关】求HACK
743014
_H17_楼主2023/11/26 18:01
#include<bits/stdc++.h>
//#define int long long 
using namespace std;
const int N=2002;
int n,m,d[N],f[N][N],g[N];
struct Point{
	int x,y;
	Point(int x=0,int y=0):x(x),y(y){}
	friend istream&operator>>(istream&in,Point&i){
		in>>i.x>>i.y;
		return in;
	}
}r,b[N],c[N];
int dis(Point a,Point b){
	return abs(a.x-b.x)+abs(a.y-b.y);
}
void Main(){
    memset(f,0x3f,sizeof(f));
	for(int i=1;i<=n;i++)
		cin>>b[i];
	for(int i=1;i<=m;i++)
		cin>>c[i];
	cin>>r;
	g[0]=0;
	for(int i=1;i<=n;i++)
		d[i]=dis(b[i],r),g[i]=g[i-1]+d[i];
	for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            f[i][j]=min({f[i][j-1],f[i-1][j]+d[i],
            min(g[i-1],f[i-1][j-1])+dis(b[i],c[j])});
        }/*
    for(int i=0;i<=n;i++)
        for(int j=0;j<=m;j++)
        	cout<<f[i][j]<<(j!=m?' ':'\n');*/
	cout<<g[n]+f[n][m]<<'\n';
	return;
}
signed main(){
	while(cin>>n>>m)
		Main();
	return 0;
}//前i个点,有j个邮递员。
//f[i][j]=f[i-1][j]+d[i];//i from R
//f[i][j]=f[i-1][j-1]+dist[i][j];
//f[i][j]=f[i][j-1];
2023/11/26 18:01
加载中...