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; } };