問題
プレイヤーは複数存在するホラー映画を観る。
各ホラー映画について、映画の長さlengthと恐いシーンが出現するときの映画開始からの長さscaryが与えられる。
長さscaryまで起きて入れば恐さの値が47加算される。
プレイヤーは最初に恐さの値を74持つ。
１分ごとに恐さの値が１ずつ減っていき、－１になると寝てしまい他の映画は見れなくなる。
複数存在するときは辞書順に小さいものを返す。
解き方
映画の数は20なので、ビット列ｄｐがなんとなく使えそう。
ただし順番を求めるため、ｄｐの値に配列を持つとメモリが足りなくなってしまう。
そこで、「映画を観た本数」の配列と「そのうち辞書順で最小の映画の順番」の配列を用意し、状態として「これまでに観た映画のビット列」を持たせる。
最後に逆順にたどることで、順番を復元することができる。
ｄｐで求めたい値が２つある場合は、今回のように最小の「映画の順番」、「映画を観た本数」の２つのｄｐを用意して解く。
コード
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()
int c[(1<<20)+1],first[(1<<20)+1];
class TheMoviesLevelTwoDivOne {
public:
vector<int> find(vector<int> length, vector<int> scary) {
int n=length.size();
memset(c,0,sizeof(c));
memset(first,0,sizeof(first));
for(int i=1;i<(1<<n);i++){
int bestcount=-1,bestfirst=0;
int score=74;
for(int j=0;j<n;j++)if(!(i&(1<<j)))score+=(47-length[j]);
for(int j=0;j<n;j++){
if(i&(1<<j)){
int count=0;
if(score>=scary[j]&&score+47-length[j]>=0){
count=c[i-(1<<j)]+1;
}
if(count>bestcount){
bestcount=count;
bestfirst=j;
}
}
}
c[i]=bestcount;
first[i]=bestfirst;
}
vector<int> ret;
int x=(1<<n)-1;
while(x>0){
ret.push_back(first[x]);
x=x-(1<<first[x]);
}
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()
int c[(1<<20)+1],first[(1<<20)+1];
class TheMoviesLevelTwoDivOne {
public:
vector<int> find(vector<int> length, vector<int> scary) {
int n=length.size();
memset(c,0,sizeof(c));
memset(first,0,sizeof(first));
for(int i=1;i<(1<<n);i++){
int bestcount=-1,bestfirst=0;
int score=74;
for(int j=0;j<n;j++)if(!(i&(1<<j)))score+=(47-length[j]);
for(int j=0;j<n;j++){
if(i&(1<<j)){
int count=0;
if(score>=scary[j]&&score+47-length[j]>=0){
count=c[i-(1<<j)]+1;
}
if(count>bestcount){
bestcount=count;
bestfirst=j;
}
}
}
c[i]=bestcount;
first[i]=bestfirst;
}
vector<int> ret;
int x=(1<<n)-1;
while(x>0){
ret.push_back(first[x]);
x=x-(1<<first[x]);
}
return ret;
}
};