为什么80分?
查看原帖
为什么80分?
948410
dws_rwhy楼主2023/6/8 10:05
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
int rank[101][101];
int lenth[101][101];
int ax[101],ay[101];
int bx[101],by[101];
int n,m,k;
int read()
{
    int s=0,w=1;
    char ch=getchar();
    while('0'>ch||ch>'9')w=ch=='-'?-1:1,ch=getchar();
    while('0'<=ch&&ch<='9')s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
    return s*w; 
}
void f(int x,int s,int t) 
{
	for(int i=s;i<=t;i++)
		lenth[i][x]=t-i+1;
}
 
int cmpx;
bool cmp(int a,int b)
{
	return lenth[cmpx][a]>lenth[cmpx][b];
}
 
bool can(int boom,int arms)
{
	return (ax[arms]-bx[boom])*(ax[arms]-bx[boom])+(ay[arms]-by[boom])*(ay[arms]-by[boom])<=k*k;
}
 
bool used[101];
int tail[101];
int ans=1000000000;
void dfs(int now,int cnt,int cnt3)
{
	if(cnt+tail[now]>=ans) return ;  
	if(now>n)
	{
		ans=cnt;
		return ;
	}
 
	int kcnt=0;
	for(int i=1;i<=m&&kcnt!=3;i++)
	if(!used[rank[now][i]]&&lenth[now][rank[now][i]]!=0)
	{
		kcnt++;
		if(kcnt==3&&cnt3==0) break;
		used[rank[now][i]]=true;
		if(kcnt==3) dfs(now+lenth[now][rank[now][i]],cnt+1,cnt3-1);
		else dfs(now+lenth[now][rank[now][i]],cnt+1,cnt3);
		used[rank[now][i]]=false;
	}
}
 
int main()
{	
n=read(),m=read(),k=read();
	for(int i=1;i<=n;i++) ax[i]=read(),ay[i]=read();
	for(int i=1;i<=m;i++)bx[i]=read(),by[i]=read();
	
	for(int i=1;i<=m;i++)
	{
		int s=1,t;
		while(s<=n)
		{
			while(s+1<=n&&can(i,s)==false) s++;
			if(can(i,s)==false) break;
			t=s;
			while(t+1<=n&&can(i,t+1)==true) t++;
			f(i,s,t);
			s=t+1;
		}
	}
	
	for(int i=1;i<=n;i++) 
	{
		cmpx=i;
		for(int j=1;j<=m;j++) rank[i][j]=j;
		sort(rank[i]+1,rank[i]+m+1,cmp);
	}
	
	for(int i=n;i>=1;i--)
		tail[i]=tail[i+lenth[i][rank[i][1]]]+1;
	
	dfs(1,0,1);  
	
	cout<<ans<<endl;
	
	return 0;
}
2023/6/8 10:05
加载中...