問題
複数の区間が与えられ、始まりの数字start[i]と終わりの数字finish[i]がわかっている。
この区間を、サブセット集合にまとめたい。
以下の条件を満たしたときにサブセット集合と呼ぶ。
・集合中の各区間に重複がないこと
・その集合に他の要素を足すと重複が出てしまうこと
このとき、サブセット集合が何通りあるか求める。
解き方
ｄｐの問題そうなのは読みとれる。
ｄｐの設計方法について考える。
区間をできるだけくっつけていき、もうくっつけることができなければその集合を答えに加えるのがよさそう。
区間をくっつけていくには、区間の初めから考えていくｄｐになりそう。
なので区間をはじめの方から走査し、前の区間がなければ最初の区間なのでｄｐに加える方法にする。
ｄｐの状態は「区間の終わりの数字」、値は「その区間の場合の数」とする。
加えていくときにそれまでの区間が存在するかはすでに判定しているので、そのような区間が存在していれば場合の数の和になっていく。
最大のstart区間より大きい数字のｄｐを足していく。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class IntervalSubsets {
public: int numberOfSubsets(vector<int> start, vector<int> finish) {
int n=start.size();
int dp[105];
memset(dp,0,sizeof(dp));
dp[0]=1;
FORE(i,0,105){
FORE(j,0,n){
if(start[j]>=i){
int ok=1;
FORE(k,0,n)if(start[k]>=i&&finish[k]<start[j])ok=0;
if(ok)dp[finish[j]+1]+=dp[i];
}
}
}
int x=0,ret=0;
FORE(i,0,n)x=max(x,start[i]);
FORE(i,x+1,105)ret+=dp[i];
return ret;
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class IntervalSubsets {
public: int numberOfSubsets(vector<int> start, vector<int> finish) {
int n=start.size();
int dp[105];
memset(dp,0,sizeof(dp));
dp[0]=1;
FORE(i,0,105){
FORE(j,0,n){
if(start[j]>=i){
int ok=1;
FORE(k,0,n)if(start[k]>=i&&finish[k]<start[j])ok=0;
if(ok)dp[finish[j]+1]+=dp[i];
}
}
}
int x=0,ret=0;
FORE(i,0,n)x=max(x,start[i]);
FORE(i,x+1,105)ret+=dp[i];
return ret;
}
};