TopCoder SRM 424 Div1 Medium StrengthOrIntellect

TopCoder 動的計画法

問題

勇者がいて、二つの能力値strengthおよびintellectを持つ。
最初二つの能力値はともに1である。


n個のクエストがあり、それぞれ一度だけ、好きな順に冒険することができる。
i番目のクエストをクリアすると、points[i]の得点がもらえ、strengthまたはintellectにこの得点を好きなように割り振って増やすことができる。


ただしi番目のクエストをするためには、strengthがstrength[i]以上またはintellectがintellect[i]以上でなくてはならない。


勇者は最大でいくつのクエストをクリアできるか、求めよ。

制約条件

strength,intellect,pointsの要素の数は相等しい。
strength[i],intellect[i],points[i]≦1000
strengthの要素の個数≦50

方針

DP.
dp[S][I]を、strengthがSでintellectがIであるような状態に到達できるかどうかとする。
能力が(S,I)と定まると、それまでにこなすことのできるクエストの集合は一意に定まり、
あまる得点も一意に定まる。


dp[S][I]は、

  • dp[S-1][I]に到達可能で、(S-1,I)の状態で余っている得点が1点以上ある
  • dp[S][I-1]に到達可能で、(S,I-1)の状態で余っている得点が1点以上ある

のどちらかが成り立つときに到達可能である。


これを更新していくようなO(max(strength)*max(intellect))のDPにより解くことができる。


というのがeditorialの解説。だったが自力で思いつかなかった。
自分の解答はメモ化+無理やり全探索。
なんだか状態数がかなり少なそうだったので全探索のコードを投げたら通ってしまった。


solve(flag,strength,intellect,point)で、
flagで表される集合のクエストをクリアし、現在の能力が(strength,intellect)で、pointの得点が余った状態をあらわす。


クリアしてないクエストで、現在の能力でクリアできるものがあったら全てクリアしてしまい少し状態を圧縮、
また、同じflagとstrengthで、より余りの得点が多い状態に既に至っていたら探索を打ち切る枝刈りを入れた。

ソースコード

最悪ケース30msくらい。DPより速い……

vi S,I,P;
int n,ans;
map<pair<ll,int>,int> dp;
void solve(ll v,int x,int y,int pt){
  rep(i,n)if(!(v&1ll<<i)&&(S[i]<=x||I[i]<=y)){
    pt+=P[i];
    v|=1ll<<i;
  }
  if(dp.count(mp(v,x))&&dp[mp(v,x)]<=y)return;
  
  dp[mp(v,x)]=y;
  ans=max(ans,__builtin_popcountll(v));
  rep(i,n)if(!(v&1ll<<i)){
    if(x+pt>=S[i])solve(v|1ll<<i,S[i],y,pt-(S[i]-x)+P[i]);
    if(y+pt>=I[i])solve(v|1ll<<i,x,I[i],pt-(I[i]-y)+P[i]);
  }
}

class StrengthOrIntellect {
  public:
  int numberOfMissions(vector <int> strength, vector <int> intellect, vector <int> points) {
    n=points.size();
    ans=0;
    dp.clear();
    S=strength; I=intellect; P=points;
    solve(0,1,1,0);
    return ans;
  }
};