状态压缩DP SRM 667 Div1 250

int dp[(1<<20)+10];
int a[55];

class OrderOfOperations {
public:
   int minTime( vector <string> s ) {
        int n = s.size (), m = s[0].length ();
        memset (a, 0, sizeof (a));
        int tot = 0;
        for (int i=0; i<n; ++i) {
            for (int j=0; j<m; ++j) {
                if (s[i][j] == ‘1‘) a[i] |= (1<<j);
            }
            tot |= a[i];
        }
        memset (dp, INF, sizeof (dp));
        dp[0] = 0;
        for (int i=0; i<(1<<m); ++i)    {
            for (int j=0; j<n; ++j) {
                int x = i | a[j];                       //从i状态转移到x的状态
                int y = x - i;                          //表示新出现的1
                int k = __builtin_popcount (y);         //内置函数，快速得到二进制下1的个数
                dp[x] = min (dp[x], dp[i] + k * k);     //类似Bellman_Ford
            }
        }

        return dp[tot];
   }
};