SRM 667 Div1 Easy Order Of Operations

どのメモリを使用したかをbitで管理する。
n個の指示を完了するためには、goal := s[0] | s[1] | ... | s[n-1] でbitの立っているメモリを少なくとも一回は使わなければならない。
逆に、goalで立っているbitに対応するメモリを全て実行したならば全ての指示は時間0で実行できる。よって、どのメモリを使用したかだけを情報としてもってbitDPをすればよい。

dp[S] := (Sに対応するメモリを実行するのにかかる時間の総和)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i, N) for (int i = 0; i < (int)N; i++)

const int INF = 1e9;

class OrderOfOperations {
public:
  vector<string> s;

  int minTime(vector<string> _s) {
    s = _s;
    int n = s.size();
    int m = s[0].size();
    vector<int> dp(1<<m, INF);
    vector<int> a(n,0);
    REP(i,n){
      REP(j,m){
        a[i] *= 2;
        a[i] += s[i][j] - '0';
      }
    }
    int goal = 0;
    REP(i,n) goal = goal | a[i];

    dp[0] = 0;
    REP(S,1<<m){
      REP(i,n){
        int T = S | a[i];
        int cst = 0;
        REP(j,m){
          if(((S >> j) & 1) ^ ((T >> j) & 1)){
            cst++;
          }
        }
        dp[T] = min(dp[T], dp[S] + cst * cst);
      }
    }
    return dp[goal];
  }
};