2 条题解
-
0
#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
#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
信息
- ID
- 372
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 6
- 标签
- 递交数
- 102
- 已通过
- 29
- 上传者