思路：
在网上跟大家交流后，才知道自己漏看了题目，后来想了想，现将思路贴出来，供大家交流
目的：最多可以取出多少个能够组成嵌套集
如果存在一个子嵌套集，而新增加的一个二段模式与子嵌套集的某个二段模式冲突（不相互嵌套），它虽然不能加入该嵌套子集，
但是它却可以和该子集中不冲突的其他二段模式组成子集，所以很难处理。因此，从这个角度来思考，太过于复杂。
从上面的思路中我们可以得到一些有用的结论：针对存在的一个子嵌套集，新的二段模式的加入，可以生成新的子嵌套集，也就
是造成分支；进一步我们可以认为，一个二段模式最多可以生成一个分支，而且一个分支主要是因为某个二段模式与其他嵌套集
冲突造成的，也就是一个二段模式可以对应一个嵌套集；n个二段模式最多组成n个独立的嵌套集。
算法流程：
1、初始n个嵌套集，分别包含编号0~n-1二段模式
2、针对某个二段模式，遍历查看是否可以满足加入嵌套集的条件（两两相互嵌套，而且该二段模式之前不存在）
满足的话，将其加入
3、找出最/大的嵌套集
[cpp] view plain copy#include <iostream> #include <sstream> #include <string> #include <vector> #include <deque> #include <cassert> #include <map> #include <algorithm> using namespace std; class interval { public: explicit interval(size_t left, size_t right) : mleft(left), mright(right) { assert(left <= right); } size_t left() const { return mleft; } size_t right() const { return mright; } /////添加 interval(){}; interval(const interval &a); interval &operator = (const interval &a); //// private: size_t mleft; size_t mright; }; ////// interval::interval(const interval &a) { this->mleft = a.mleft; this->mright = a.mright; } interval &interval::operator =(const interval &a) { this->mleft = a.mleft; this->mright = a.mright; return *this; } ///// inline bool operator<(const interval& a, const interval& b) { return a.right() < b.left(); } class twointerval { public: explicit twointerval(const interval& left, const interval& right) : mleft(left), mright(right) { assert(left < right); } const interval& left() const { return mleft; } const interval& right() const { return mright; } /////添加 twointerval(){}; twointerval(const twointerval &a); twointerval &operator = (const twointerval &a); //// private: interval mleft; interval mright; }; ////// twointerval::twointerval(const twointerval &a) { this->mleft = a.mleft; this->mright = a.mright; } twointerval &twointerval::operator=(const twointerval &a) { this->mleft = a.mleft; this->mright = a.mright; return *this; } ///// inline bool within(const twointerval& a, const twointerval& b) { return b.left() < a.left() && a.right() < b.right(); } void input(vector<twointerval>& twos) { int m = 0; { string s; getline(cin, s); istringstream is(s); is >> m; } for (int i = 0; i < m; ++i) { string s; getline(cin, s); istringstream is(s); size_t a, b, c, d; is >> a >> b >> c >> d; interval left(a, b); interval right(c, d); twos.emplace_back(left, right); } } // ====== 填入你自己的逻辑 ======== /////********************************///// /* 目的：最多可以取出多少个能够组成嵌套集 思路： 如果存在一个子嵌套集，而新增加的一个二段模式与子嵌套集的某个二段模式冲突（不相互嵌套），它虽然不能加入该嵌套子集， 但是它却可以和该子集中不冲突的其他二段模式组成子集，所以很难处理。因此，从这个角度来思考，太过于复杂。 从上面的思路中我们可以得到一些有用的结论：针对存在的一个子嵌套集，新的二段模式的加入，可以生成新的子嵌套集，也就 是造成分支；进一步我们可以认为，一个二段模式最多可以生成一个分支，而且一个分支主要是因为某个二段模式与其他嵌套集 冲突造成的，也就是一个二段模式可以对应一个嵌套集；n个二段模式最多组成n个独立的嵌套集。 算法流程： 1、初始n个嵌套集，分别包含编号0~n-1二段模式 2、针对某个二段模式，遍历查看是否可以满足加入嵌套集的条件（两两相互嵌套，而且该二段模式之前不存在） 满足的话，将其加入 3、找出最/大的嵌套集 */ /////********************************///// inline bool operator==(const interval& a, const interval& b) { return (a.right() == b.right()) && (a.left() == b.left()); } inline bool operator==(const twointerval& a, const twointerval& b) { return (a.right() == b.right()) && (a.left() == b.left()); } bool confl(const twointerval& a, const twointerval& b) { if (!(within(a, b) || within(b, a))) return true; if (a == b) return true; return false; } bool add(vector<twointerval> &a, twointerval b) { for (twointerval ti : a) { if (confl(ti,b)) { return false; } } a.push_back(b); return true; } int intussusception(vector<twointerval>& two2) { int len = two2.size(); if (len < 2) return len; int max = 0; vector<vector<twointerval> > res(len); for (int i = 0; i < len; i++) { res[i].push_back(two2[i]); } for (int i = 0; i < len; i++) { for (int j = 0; j < len; j++) { add(res[j], two2[i]); } } for (int i = 0; i < len; i++) { if (res[i].size()>max) { max = res[i].size(); } } return max; } // ====== 结束 ======== int main() { vector<twointerval> twos; input(twos); cout << intussusception(twos) << endl; return 0; }
西安飞凡网络技术咨询有限公司
400 011 2010