TopCoder SRM 362 Div1 Medium PartialSeries

問題

n項からなる数列において、i番目の項が極値であるとは、
1＜i＜nかつ、a[i-1]＜a[i]＞a[i+1]または、a[i-1]＞a[i]＜a[i+1]が成り立つことを言う。
（最初の項または最後の項は極値にはならない）

数列のうち、いくつかの項が-1に置き換わったものが与えられる。
それぞれの-1に、available[]の数字どれかを入れて（それぞれの数字は一度までしか使えない）
数列を復元したときに、極値の数がなるべく少なくなるようにしたい。

そのような数列を求めよ。
ただし、答えが複数あるときは、第一項がなるべく小さいものを、
それも複数あるときは二番目の項がなるべく小さいものを……というようにして答えを選ぶものとする。

制約条件

• 1≦数列の各項≦10

数列の項≦50
available[i]≦10
availableの要素数≦15

方針

直前および2個前に使った数と、availableのうちで使った集合を覚えるメモ化再帰+経路復元
ただし、dp[pos][prev1][prev2][mask]のようにすると、状態が大きくなりすぎるので、
posは覚えないようにする。
それで、-1が出現するまでposを飛ばすようにして状態を圧縮する。

メモ化再帰を経路復元するときは頭からできる。

ソースコード

bool ck(int a,int b,int c){
  return b>a&&b>c||b<a&&b<c;
}
vi S,A;
int n,m;
int dp[11][11][1<<15],next[11][11][1<<15];
int rec(int pos,int p,int pp,int mask){
  int cp=p, cpp=pp, cnt=0;
  
  for(;pos<n&&S[pos]>=0;pos++){
    if(pos>1&&ck(cpp,cp,S[pos]))cnt++;
    cpp=cp; cp=S[pos];
  }
  if(pos>=n)return cnt;
  
  int &ret=dp[p][pp][mask];
  if(ret>=0)return ret;
  ret=inf;
  rep(i,m)if(mask&1<<i){
    int tmp=rec(pos+1,A[i],cp,mask^1<<i)+(pos>1&&ck(cpp,cp,A[i]));
    if(tmp<ret)ret=tmp, next[p][pp][mask]=i;
  }
  ret+=cnt;
  return ret;
}
class PartialSeries {
  public:
  vector <int> getFirst(vector <int> series, vector <int> available) {
    S=series; A=available;
    n=S.size(); m=A.size();
    sort(all(A));
    
    memset(dp,-1,sizeof(dp));
    rec(0,0,0,(1<<m)-1);
    int pos=0, p=0, pp=0, mask=(1<<m)-1;
    vi ans;
    for(;pos<n;pos++){
      int cp=p, cpp=pp, nmask=mask^1<<next[p][pp][mask];
      for(;pos<n&&S[pos]>=0;pos++){
        ans.pb(S[pos]);
        cpp=p; cp=S[pos];
      }
      if(pos>=n)break;
      p=A[next[p][pp][mask]];
      pp=cp;
      ans.pb(p);
      mask=nmask;
    }
    return ans;
  }
};