SRM 588 DIV1 Middle - KeyDungeonDiv1 （復習×）
問題
最初に赤い鍵をkey[0]個、緑の鍵をkey[1]個、白い鍵をkey[2]個与えられる。
ドアが複数存在し、ドアごとに空けるために必要な赤い鍵の数、緑の鍵の数がわかっている。また、ドアを開けた時に得られる各色の鍵の数が与えられる。
ドアを空けるためには必要な赤い鍵の数、緑の鍵の数を持っていないといけないが、
白い鍵は赤い鍵もしくは緑の鍵として代用できる。
ドアを開けたら使った鍵はなくなってしまう。
またプレイヤーは好きなところでドアを開けるのをやめてもよい。
このとき、持っている鍵の数が最大となるときの鍵の合計数を求める。
解き方
最初に白い鍵はできるだけ消費しないように貪欲に解けると思ったが、
空けるドアの順番によって白い鍵の数が変わってしまうため貪欲法では解けない。
そのため、すでに空けたドアを状態に持つＤＰでは解けない。
そこで、白い鍵を赤とみなすか、緑とみなすか全ての場合を考えれば全ての鍵の使い方を探索することができる。
つまり、すでに空けたドアに加え、白い鍵を赤とみなす数を状態に持つＤＰを用いれば解くことができる。
今回は鍵の数を返り値にもつＤＦＳではなく、グローバルで答えを更新した方が単純なコードになる。
コード
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 n,dp[(1<<12)][131],best;
vector<int> doorR,doorG,roomR,roomG,roomW,keys;
class KeyDungeonDiv1 {
public:
void dfs(int mask,int w){
if(dp[mask][w])return;
dp[mask][w]=1;
int r=keys[0]+w,g=keys[1]+keys[2]-w;
FORE(i,0,n){
if(mask&(1<<i)){
r+=roomR[i]-doorR[i];
g+=roomG[i]-doorG[i]+roomW[i];
}
}
best=max(best,r+g);
FORE(i,0,n){
if(mask&(1<<i))continue;
if(r>=doorR[i]&&g>=doorG[i]){
FORE(j,0,roomW[i]+1){
dfs(mask|(1<<i),w+j);
}
}
}
}
int maxKeys(vector<int> doorR_, vector<int> doorG_, vector<int> roomR_, vector<int> roomG_, vector<int> roomW_, vector<int> keys_) {
doorR=doorR_,doorG=doorG_;
roomR=roomR_,roomG=roomG_,roomW=roomW_;
keys=keys_;
n=doorR.size();
memset(dp,0,sizeof(dp));
best=0;
FORE(i,0,keys[2]+1)dfs(0,i);
return best;
}
};
#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 n,dp[(1<<12)][131],best;
vector<int> doorR,doorG,roomR,roomG,roomW,keys;
class KeyDungeonDiv1 {
public:
void dfs(int mask,int w){
if(dp[mask][w])return;
dp[mask][w]=1;
int r=keys[0]+w,g=keys[1]+keys[2]-w;
FORE(i,0,n){
if(mask&(1<<i)){
r+=roomR[i]-doorR[i];
g+=roomG[i]-doorG[i]+roomW[i];
}
}
best=max(best,r+g);
FORE(i,0,n){
if(mask&(1<<i))continue;
if(r>=doorR[i]&&g>=doorG[i]){
FORE(j,0,roomW[i]+1){
dfs(mask|(1<<i),w+j);
}
}
}
}
int maxKeys(vector<int> doorR_, vector<int> doorG_, vector<int> roomR_, vector<int> roomG_, vector<int> roomW_, vector<int> keys_) {
doorR=doorR_,doorG=doorG_;
roomR=roomR_,roomG=roomG_,roomW=roomW_;
keys=keys_;
n=doorR.size();
memset(dp,0,sizeof(dp));
best=0;
FORE(i,0,keys[2]+1)dfs(0,i);
return best;
}
};
