imported>molid7 at 06:16, 21 August 2012

2012-08-21T06:16:06Z

New page

#include<iostream>
#include<vector>
#include <algorithm>

using namespace std;

bool chain(pair<int, int> &p1, pair<int, int> &p2) {
if(
(p1.first > p2.first && p1.second < p2.second) ||
(p1.first == p2.first && p1.second < p2.second) ||
(p1.first > p2.first && p1.second == p2.second)
) return true;

if(
(p1.first < p2.first && p1.second > p2.second) ||
(p1.first == p2.first && p1.second > p2.second) ||
(p1.first < p2.first && p1.second == p2.second)
) return true;

return false;
}

class op {
public:
bool operator() (pair<int, int> &p1, pair<int, int> &p2) {
if(p1.first != p2.first)
return p1.first < p2.first;
else
return p1.second > p2.second;
}
}myOp;

int main() {
vector<pair<int,int>> vc;
vector<int> vd;
vc.push_back(make_pair(0,0));
vd.push_back(0);

int t, dummy, s, e;
cin>>t;
while(t--) {
cin>>dummy>>s>>e;
vc.push_back(make_pair(s,e));
}

vd.resize(vc.size());
for(int i=1; i<vd.size(); i++)
vd[i] =1;

sort(vc.begin() +1 , vc.end(), myOp);

for(int i=2; i<vc.size(); i++) {
for(int j=i-1; j>0; j--) {
if(chain(vc[i], vc[j])) {
vd[i] = vd[j] +1;
break;
}
}
}

int max = vd[1];
for(int i=2; i<vd.size(); i++)
if(max < vd[i]) max = vd[i];

cout<<max<<endl;
return 0;
}

Koi cha/곽병학 - Revision history

imported>molid7 at 06:16, 21 August 2012