Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
52466 | AK2022071326 | 木板游戏 | C++ | 运行超时 | 60 | 2000 MS | 4804 KB | 469 | 2022-07-19 12:15:11 |
#include<bits/stdc++.h> using namespace std; int n; struct node{ int x; int y; } a[500010]; bool cmp(node x,node y) { return x.y-x.x>y.y-y.x; } long long ans,dp[500010]; int main() { cin>>n; for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].y; sort(a+1,a+1+n,cmp); for(int i=1;i<=n;i++) { for(int j=1;j<i;j++) if(a[i].x>=a[j].x&&a[i].y<=a[j].y) dp[i]=max(dp[i],dp[j]); dp[i]++; ans=max(ans,dp[i]); } cout<<ans<<endl; return 0; }