WARush

SRMの結果とか、解けた問題のコードを書いていきます

SRM667 Div1 Easy "OrderOfOperations"

解法

dpる。

dp[bit] := メモリの使用状態がbitとするときの、最小時間
dp初期化

メモリを全く使用しない場合、つまりプログラムを動かさないときの時間は0であるため、

dp[0] = 0;
dp更新

現在考えている命令が使用するメモリをnum、現在考えているメモリを状態をbitとすると、
命令を実行するときにかかる時間はcost = num xor (bit & num)となる。

dp[bit | num] = min(dp[bit | num], dp[bit] + cost^2)
dp答え

全ての命令を実行したときの使用メモリの状態をansBitとすると

dp[ansBit]

事後

貪欲でいっちまったぁぁ

ソースコード

const int INF = 500;
int num[55];
int dp[1 << 20];

class OrderOfOperations {
    public:
    int minTime(vector<string> s) {
        int n = s.size();
        int m = s[0].size();

        // num初期化
        for (int i = 0; i < n; i++) {
            int t = 0;
            for (int j = 0; j < m; j++) {
                if (s[i][j] == '1') t++;
                if (j != m - 1) t <<= 1;
            }
            num[i] = t;
        }

        // dp初期化
        for (int b = 0; b < 1 << m; b++) {
            dp[b] = INF;
        }
        dp[0] = 0;

        for (int b = 0; b < 1 << m; b++) {
            if (dp[b] == INF) continue;
            for (int i = 0; i < n; i++) {
                int nb = b | num[i];
                int newM = __builtin_popcount(num[i] ^ (b & num[i]));
                dp[nb] = min(dp[nb], dp[b] + newM * newM);
            }
        }

        int ansBit = 0;
        for (int i = 0; i < n; i++) {
            ansBit |= num[i];
        }

        return dp[ansBit];
    }
};