TopCoder SRM 387 DIv1 Medium IntervalSubsets

問題

n個の区間が与えられる。
それぞれの開始はstart[i]であり、終了はfinish[i]である。


この区間から、次の条件を満たす部分集合を選びたい。

  • 部分集合に属する、どの二つの異なる区間も交わっていない(共通部分を持たない)
  • 部分集合に属さない区間を、一つも加えることができない

条件を満たす部分集合の選び方の場合の数を求めよ。

制約条件

n≦50
start[i],end[i]≦100

方針

DP.
dp[i]を、最後に使った区間の数字がiであり、かつ他に区間を加えられなかったような状態の場合の数とする。
次に加えられる区間は、

■■■■■■
  ■■■■■
    ■■■■■
      □□□□□

上の黒い四角のような区間
すなわち、iより後ろにある区間のうち、最も最初に終了する区間と交わる区間のどれか。


次に加えられる区間がなかったら、それは条件を満たす区間なので、
その数は答えに足す。

ソースコード

int n,dp[101];

class IntervalSubsets {
  public:
  int numberOfSubsets(vector <int> start, vector <int> finish) {
    n=start.size();
    memset(dp,0,sizeof(dp));
    dp[0]=1;
    int ans=0;
    for(int i=0;i<=100;i++){
      int mn=inf;
      rep(j,n)if(start[j]>i)mn=min(mn,finish[j]);
      if(mn==inf){
        ans+=dp[i];
        continue;
      }
      rep(j,n)if(i<start[j]&&start[j]<=mn)dp[finish[j]]+=dp[i];
    }
    return ans;
  }
};