求大佬指点一下江山, WA数据,好奇的可以看这里
#include <iostream>
#include <cmath>
using namespace std;
typedef long long shuju;
struct zuobiao
{
shuju x;
shuju y;
};
//想用递归解决动态规划
shuju jisuan(shuju tag,zuobiao a[],shuju n,shuju d,shuju t)
{
for(int i=0;i<n;i++) //判断下一个点
{
shuju p=0; //和tag一样,用于累加,最后和tag比较
shuju k=t; //剩余点数,k的替代
if(a[d].x<=a[i].x&&a[d].y<=a[i].y&&i!=d)//d用于计算上一位,确保点位够
{
if((a[i].x-a[d].x)+(a[i].y-a[d].y)<=k)//判断点位是否够
{
k-=(a[i].x-a[d].x)+(a[i].y-a[d].y);//--
}
d=i;
p+=jisuan(p,a,n,d,k);//递归,找下一个点
if((p+t)>=tag)//比较
{
tag=p+t;
}
}
}
return tag;
}
int main()
{
shuju n=0;
shuju k=0;
shuju tag=0;
cin>>n>>k;
zuobiao a[510];
for(shuju i=0;i<n;i++)
{
cin>>a[i].x>>a[i].y;
}
shuju d=0;
cout<<jisuan(tag,a,n,d,k)<<endl;
return 0;
}