2 条题解

  • 0
    @ 2025-10-8 16:49:57
    #include<bits/stdc++.h>
    using namespace std;
    const int N=5100;
    struct tree {int a,b;}tr[2*N];
    int f[N][N],q[N];
    int main() 
    {
        int n,d,m;scanf("%d%d%d",&n,&d,&m);
        for(int i=1; i<=n; i++)scanf("%d%d",&tr[i].a,&tr[i].b);
        memset(f,0,sizeof(f));
        int ans=f[1][0]=tr[1].a;
        for(int j=1; j<=m; j++) 
    	{
            int l=1,r=1;q[1]=0;
            for(int i=1; i<=n; i++) 
    		{
                while(l<=r && tr[i].b-tr[q[l]].b >d )l++;
    			f[i][j]=(l<=r)?f[q[l]][j-1] + tr[i].a:0;ans=max(ans,f[i][j]);
    			while(l<=r && f[q[r]][j-1]<=f[i][j-1])r--;
                if(f[i][j-1])q[++r]=i; 
            }
        }
        printf("%d\n",ans);
        return 0;
    }
    
    • 0
      @ 2025-10-8 16:49:49
      #include<bits/stdc++.h>
      using namespace std;
      const int N=5100;
      struct tree {int a,b;}tr[2*N];
      int f[N][N],q[N];
      int main() 
      {
          int n,d,m;scanf("%d%d%d",&n,&d,&m);
          for(int i=1; i<=n; i++)scanf("%d%d",&tr[i].a,&tr[i].b);
          memset(f,0,sizeof(f));
          int ans=f[1][0]=tr[1].a;
          for(int j=1; j<=m; j++) 
      	{
              int l=1,r=1;q[1]=0;
              for(int i=1; i<=n; i++) 
      		{
                  while(l<=r && tr[i].b-tr[q[l]].b >d )l++;
      			f[i][j]=(l<=r)?f[q[l]][j-1] + tr[i].a:0;ans=max(ans,f[i][j]);
      			while(l<=r && f[q[r]][j-1]<=f[i][j-1])r--;
                  if(f[i][j-1])q[++r]=i; 
              }
          }
          printf("%d\n",ans);
          return 0;
      }
      • 1

      *【单调队列:二维DP】猴子吃香蕉[GDKOI2007改编]

      信息

      ID
      372
      时间
      1000ms
      内存
      512MiB
      难度
      6
      标签
      递交数
      102
      已通过
      29
      上传者