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