luogu P2439 [SDOI2005]阶梯教室设备利用

阶梯教室设备利用"/>

luogu P2439 [SDOI2005]阶梯教室设备利用

题目链接

luogu P2439 [SDOI2005]阶梯教室设备利用

题解

dp

代码

#include<vector> 
#include<cstdio> 
#include<cstring> 
#include<algorithm> 
#define LL long long
inline int read() { int x = 0,f = 1;char c = getchar(); while(c < '0'||c > '9')c = getchar(); while(c <= '9' &&c >= '0')x = x * 10 + c - '0',c = getchar(); return x * f; 
} const int maxn = 30007; 
int l[maxn],r[maxn]; 
int n,dp[maxn]; 
std::vector<int>vec[maxn]; 
int mx = 0; 
int main() { n = read(); for(int i = 1;i <= n;++ i) { l[i] = read();r[i] = read(); vec[r[i]].push_back(l[i]);      mx = std::max(mx,r[i]); } for(int i = 1;i <= mx;++ i) { dp[i] = dp[i - 1]; for(int j = 0;j < vec[i].size();++ j) { dp[i] = std::max(dp[i],dp[vec[i][j]] + (i - vec[i][j])); } } printf("%d\n",dp[mx]); return 0; 
} 

转载于:.html