ABC271 D - Flip and Adjust

DはDPのD

アウトプットのオタクになります。

僕が考えたことメモなので解説ではありません。悪しからず

DPを考える

ナップサックみたい解いてあげれば出来ます、あんまりよくない復元の仕方してるかもしれないけど出来たのでヨシ！

REを踏んだんですけどこんな感じでいけました

REP(i,N+1){
   REP(j,S+2){
   if(j>=a[i]){if(dp[i][j-a[i]]!="x")dp[i+1][j]=dp[i][j-a[i]]+'H';}
     if(j>=b[i]){if(dp[i][j-b[i]]!="x")dp[i+1][j]=dp[i][j-b[i]]+'T';}
  }
}

なんかできました。

dp[i番目までカードを使ったとき][合計j]＝それを満たす裏表の文字列

みたいにしてあげました。えいやっってやったら通ってしまったのでヨシ。

個人的ポイント

ナップサックの亜種に見えたのでなんかうまいこと使えないか考えてみるとできました