SRM387 div1 medium
動物的直感でAC。
#include <algorithm> #include <cstdio> #include <cstring> #include <utility> #include <vector> using namespace std; class IntervalSubsets { public: int n; int cache[55]; vector<pair<int,int> > interval; int rec(int p) { int &r=cache[p]; if(r!=-1) return r; else { r=0; int ss=interval[p].second+1,se; for(int i=0;i<n;i++) if(ss<=interval[i].first) { se=interval[i].second; break; } for(int i=0;i<n;i++) if(ss<=interval[i].first && interval[i].first<=se) { r+=rec(i); se=min(se,interval[i].second); } return (r!=0)?r:r=1; } } int numberOfSubsets(vector <int> start, vector <int> finish) { interval.clear(); start.push_back(0); finish.push_back(0); n=start.size(); for(int i=0;i<n;i++) interval.push_back(make_pair(start[i],finish[i])); sort(interval.begin(),interval.end()); memset(cache,-1,sizeof(cache)); return rec(0); } };