2

ここでこの問題を解決しようとしていました。

また、質問を投稿してください：N間隔のリストが与えられます。課題は、サブセット内の 3 つの間隔が共通点を共有しないように、間隔の最大のサブセットを選択することです?

しかし、解決には至りませんでした。これは私がこれまでに試したことです：

  1. DP: 問題にサブ問題が重複しているとは思わないので、これは機能しませんでした
  2. 各ポイントが頂点であり、間隔が無向グラフのエッジであるグラフに縮小しました。次に、問題は、グラフ内の最大長の互いに素なパスを見つけることになります。これもきちんとした方法を思いつくことができませんでした
  3. それをネットワークフローに減らしてみましたが、うまくいきませんでした。

この問題にアプローチする方法、または何か不足している場合のヒントを教えてください。申し訳ありませんが、私は本当に長い間アルゴリズムをやっていて、最近連絡が取れていません。

4

2 に答える 2

3

プログラミングせずに、一般的な言葉で解決策を示します。

セグメントを s 1、s 2、...、s nとします。それらの始まりは b 1、 b 2、... b nであり、終わりは e 1、 e 2、... e nです。

b 1 < b 2 <...< b nのように、セグメントを先頭で並べ替えます。点を覆う 3 つのセグメントがないという条件が成立するかどうかを確認するだけで十分です。b 1から b nの順番でやっていきます。したがって、b 1から開始し、次の点に移動するというように 1 つずつ、ある点 b iでそれを覆う 3 つのセグメントが存在するまで続けます。これらは、s iと他の 2 つのセグメントになります。たとえば、s jと s kとします。これらの 3 つのセグメントのうち、最大の終点を持つセグメント、つまり max{e i , e j , e kを削除します。}。次のセグメント (b i+1 ) の先頭に移動します。b nに到達すると、プロセスは完了です。残されたすべてのセグメントは、セグメントの最大のサブセットを構成し、3 つのセグメントが共通点を共有することはありません。

これが最大サブセットになる理由。解が S (セグメントのセット) だとしましょう。最適解 S* があるとします。ここでも、S と S* のセグメントを開始位置の座標で並べ替えます。ここで、S と S* のセグメントを調べて、それらの終点を比較します。S の任意の k番目のセグメントに対する S の構成により、その終了座標はS*の k番目のセグメントの終了座標よりも小さくなります (e k <=e k )。したがって、S 内のセグメントの数は S 内よりも少なくありません(S* 内を移動すると、常に S を追い越します)。

これが十分に説得力がない場合は、最初に、2 つのセグメントが重なってはならない、より単純な問題について考えてみてください。解は同じですが、正しい答えが得られる理由をより直感的に理解できます。

于 2012-05-31T18:44:13.393 に答える
2

シャファは正しい。

#include <iostream>
#include <set>

using namespace std;

class Interval{
public:
int begin;int end;
Interval(){
    begin=0;end=0;
}

Interval(int _b,int _e){
    begin=_b;end=_e;
}

 bool operator==(const Interval& i) const {
     return (begin==i.begin)&&(end==i.end);
 }

 bool operator<(const Interval& i) const {
     return begin<i.begin;
 }
};

int n,t,a,b;
multiset<Interval> inters;
multiset<int> iends;

multiset<Interval>::iterator it1;
multiset<int>::iterator et1;

int main(){
scanf("%d",&t);
while(t--){
    inters.clear();
    iends.clear();
    scanf("%d",&n);
    while(n--){
        scanf("%d %d",&a,&b);
        Interval inter(a,b);
        inters.insert(inter);
    }
    it1=inters.begin();
    while(it1!=inters.end()){
        iends.insert(it1->end);
        et1=iends.lower_bound(it1->begin);
        multiset<int>::iterator t=et1;
        if((++et1!=iends.end())&&(++et1!=iends.end())){
            //把剩下的线段全部删掉
            while(et1!=iends.end()){
                multiset<int>::iterator te=et1;
                et1++;
                iends.erase(te);
            }
        }
        it1++;
    }
    printf("%d\n",iends.size());
}
system("pause");
return 0;
}
于 2012-09-23T03:17:24.670 に答える