求大佬指点一下!
查看原帖
求大佬指点一下!
843406
sjm2022楼主2024/8/6 11:12

求大佬指点一下江山, 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;
}
2024/8/6 11:12
加载中...