SRM 667 div1 easy:OrderOfOperations
SRM 667 に参加しました。
見事に貪欲解法にハマって 0 完です。久しぶりのプログラミングコンテストなのでレート下がるだろうとは思っていたんですがなんか悔しいレートの下がり方をした感じですね。
解法
bitDP で解きます。
dp[state] = (メモリを state だけ使った場合の最小コスト)とすると, state の状態になった時点で行った操作はちゃんとわかります(すでに消費したメモリの中に操作したメモリが含まれているので)。
なので, 単純に各 state から n 通りの遷移をすると考えて dp すれば良いです。
得た知見
- 今回のように bit で状態を管理するタイプの DP はその state 自体で調べる範囲を狭くできることがあることは意識するべき
const int INF = 1000000; int dp[1<<22]; class OrderOfOperations { public: int minTime(vector <string> s) { int n = s.size(); int m = s[0].size(); int xx = 0; vector<int> d; for (int i = 0; i < n; i++) { int tmp = 0; for (int j = 0; j < m; j++) if (s[i][j] == '1') tmp |= 1<<j; d.push_back(tmp); xx |= tmp; } for (int i = 0; i < (1<<m); i++) dp[i] = INF; dp[0] = 0; for (int i = 0; i < (1<<m); i++) { if (dp[i] == INF) continue; for (int el : d) { int k = 0; for (int j = 0; j < m; j++) { if ((el>>j)&1) if (((i>>j)&1)==0) { k++; } } dp[i|el] = min(dp[i|el], dp[i]+k*k); } } return dp[xx]; } };