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]; } };