C - 積み上げパズル

DP[ とった色のhash ][ 前の色 ] = スコア でDP管理。
全色ボーナスは、とった色のhashで判断。
コンボボーナスは、前の色で判断できました。
O(5000 * 1<<10 * 10) のはずだけど8ms。

Q. DP初期値は？
A. ボーナス点にマイナスが入りうるので、DP = -INF。
Q. 解答は？
A. 最終状態のすべてのDP[ hash ][ 前色 ] を見て、最大値が解答。

1. 落ちてくる色を順番に処理していきます。
2. コンボかどうかは、前の色と同じかどうか、で判定をします。
2. DPを回す際に、hash値の論理和を使うのですが

1<<m -> 0 まで j を走査させる。

chmax(DP[j|(1<<c)][c], nxp);

0 から走査させちゃうと、重複カウントするので上から走査させます。
2. また、コンボ判定を先に走査しないと、重複カウントしちゃいます。

   rep(_p, m){
     ll p=(_p+c)%m; // 前の色。_p=0のときにコンボ判定対象から行う

3. 全色ボーナスはすべての落ちものを見終えてから清算。

 rep(p, m) if(DP[(1<<m)-1][p] != -oo) DP[(1<<m)-1][p] += Z;

実装。

ll DP[1<<10][10];
ll n, m, Y, Z;
map<char, ll> color;
ll P[11];

int main(){
 cincout();
 
 cin >> n >> m >> Y >> Z;
 rep(i, (1<<m)) rep(p, m) DP[i][p] = -oo;
 
 ll id = -1;
 ll ans = 0;
 rep(i, m){
   char c;
   ll p;
   cin >> c >> p;
   color[c] = ++id;
   P[id] = p;
 }
 rep(i, n){
   char b;
   cin >> b;
   
   ll c = color[b]; // RGBをidにしたもの
   rep(_p, m){
     ll p=(_p+c)%m; // 前の色。コンボ判定を先に行いたい
     for(ll j=(1<<m)-1; j>=0; --j){
       if (DP[j][p] == -oo) continue;
       ll nxp = DP[j][p]+P[c];
       // 色が前と同じで、cをとったことがあればコンボ判定
       if (c==p && ((j>>c)&1)) nxp += Y;
       chmax(DP[j|(1<<c)][c], nxp);
     }
   }
   // ここではじめてとった場合
   chmax(DP[1<<c][c], P[c]);
 }
 // 全色ボーナス
 rep(p, m) if(DP[(1<<m)-1][p] != -oo) DP[(1<<m)-1][p] += Z;
 rep(p, m) rep(j, (1<<m)){
   chmax(ans, DP[j][p]);
 }
 cout << ans << endl;
}

https://atcoder.jp/contests/arc010/submissions/26380633