URAL 1203 Scintific Coference簡単dp難易度:0
1038 ワード
http://acm.timus.ru/problem.aspx?space=1&num=1203
終了時間を主とし、開始時間をセカンダリとすると、任意の終了時間tについては、これまでに終了したジョブはすでに処理されており、この時間から開始するジョブはすべて処理されています.
t<=3 e 5ですので、簡単なdpで解決できます.
終了時間を主とし、開始時間をセカンダリとすると、任意の終了時間tについては、これまでに終了したジョブはすでに処理されており、この時間から開始するジョブはすべて処理されています.
t<=3 e 5ですので、簡単なdpで解決できます.
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=1e5+5;
int n;
typedef pair<int,int> P;
P t[maxn];
int dp[maxn];
int ans;
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d%d",&t[i].first,&t[i].second);
}
sort(t,t+n);
for(int i=1,j=0;i<=30001;i++){
ans=max(ans,dp[i-1]);
if(j==n||i<t[j].first)continue;
while(t[j].first==i){
dp[t[j].second]=max(dp[t[j].second],ans+1);
j++;
}
}
printf("%d
",ans);
return 0;
}