CSP-J T4 WA on #11 15 13
查看原帖
CSP-J T4 WA on #11 15 13
352426
就决定是你辣楼主2022/10/29 17:06

请问一下可能是哪里出锅了

#include<bits/stdc++.h>
using namespace std;
double d[505][505];
int ans=0;
vector<int>p[505];
struct node{
	double x,y;
}a[505];
bool cmp(node c,node b){
	if(c.x==b.x)return c.y<b.y;
	else return c.x<b.x;
}
int f[505][105];
int n,k;
int main(){
	freopen("point.in","r",stdin);
	freopen("point.out","w",stdout);
	cin>>n>>k; 
	for(int i=1;i<=n;i++){
		cin>>a[i].x>>a[i].y;
	}
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			double xi=abs(a[i].x-a[j].x);
			double yi=abs(a[i].y-a[j].y);
			d[i][j]=d[j][i]=sqrt(xi*xi+yi*yi);
			if(a[i].y<=a[j].y){
				p[j].push_back(i);
			}
		}
	}
	for(int i=1;i<=n;i++){
		f[i][0]=1;
		for(int j=0;j<p[i].size();j++){
			int v=p[i][j];
			if(d[i][v]<=1.00){
				f[i][0]=max(f[i][0],f[v][0]+1);
			}
		}
	}
	for(int h=1;h<=k;h++){
		for(int i=1;i<=n;i++){
			for(int j=0;j<p[i].size();j++){
				int v=p[i][j];
				if(d[i][v]<=1.00){
					f[i][h]=max(f[i][h],f[v][h]+1);
				}
				else {
					int cost=d[i][v];
					if(d[i][v]==cost)cost--;
					if(cost<=h)f[i][h]=max(f[i][h],f[v][h-cost]+cost+1);
				}
				
			}f[i][h]=max(f[i][h],f[i][h-1]+1);
		}
	}
	for(int i=1;i<=n;i++){
		ans=max(ans,f[i][k]);
	}
	cout<<ans<<endl;

}
2022/10/29 17:06
加载中...