社区讨论

求大佬指点一下!

P8816[CSP-J 2022] 上升点列参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@lzhulhdx
此快照首次捕获于
2024/08/06 11:15
2 年前
此快照最后确认于
2024/08/06 12:03
2 年前
查看原帖
求大佬指点一下江山, WA数据,好奇的可以看这里
CPP
#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;
}

回复

0 条回复,欢迎继续交流。

正在加载回复...