为什么会WA呀
查看原帖
为什么会WA呀
555513
yangtinghao楼主2022/11/1 21:02

应该有50的呀

#include<bits/stdc++.h>
using namespace std;
struct node
{
	int x,y;
}a[505];
int n,k,f[505],ans=-1,s[505][105];
bool cmp(node a,node b){return a.x+a.y<b.x+b.y;}
void dfs(int x,int cnt,int sum)
{
	if (cnt+k<s[cnt][sum]) return;
	s[cnt][sum]=cnt+k;
	if (x==1)
	{
		ans=max(ans,cnt+k);
		return;
	}
	for (int i=x-1;i>=1;--i)
	{
		int p=abs(a[x].x-a[i].x)+abs(a[x].y-a[i].y);
		if (sum-p+1>=0&&a[x].x>=a[i].x&&a[x].y>=a[i].y) dfs(i,cnt+1,sum-p+1);
	}
}
int main()
{
	cin>>n>>k;
	for (int i=1;i<=n;++i) cin>>a[i].x>>a[i].y;
	sort(a+1,a+n+1,cmp);
	if (k==0)
	{
		f[1]=1;
		for (int i=2;i<=n;++i)
		{
			int maxn=-1;
			for (int j=i-1;j>=1;--j) if (abs(a[i].x-a[j].x)+abs(a[i].y-a[j].y)==1&&a[i].x>=a[j].x&&a[i].y>=a[j].y&&f[j]>maxn) maxn=f[j];
			f[i]=maxn+1;
		}
		for (int i=1;i<=n;++i) ans=max(ans,f[i]);
		cout<<ans;
		return 0;
	}
	memset(s,-1,sizeof s);
	for (int i=1;i<=n;++i) dfs(i,1,k);
	cout<<ans;
	return 0;
}
2022/11/1 21:02
加载中...