1 条题解

  • 1
    @ 2025-7-7 16:14:24

    不难想到,要先按金币的出现时间排序,出现早的金币在前面

    f[i] 表示前 i 个出现的金币,第 i 个金币一定拿到,最多可以拿到的金币个数,则 ans=max(ans,f[i]);

    转移: f[i]=max(f[i], f[j]+1) 其中 j 是枚举上一个拿到的金币

    每个金币有两个域:出现时间 a[i].t 和出现地点 a[i].id

    for(int i=1;i<=n;i++)
      for(int j=0;j<i;j++)
        if(t[a[j].id][a[i].id]+a[j].t<=a[i].t)
    		f[i]=max(f[i],f[j]+1),ans=max(ans,f[i]);
    
    • 1

    信息

    ID
    315
    时间
    1000ms
    内存
    256MiB
    难度
    8
    标签
    (无)
    递交数
    60
    已通过
    10
    上传者