Top

(ΦωΦ)＜これの答えですよー。目次はここ。

---
問3-2
(ΦωΦ)＜再帰 解き方 その1 
#include <iostream>
#include <algorithm>
using namespace std;

class OrderOfOperationsDiv2 { public: int minTime(vector<string> s); };

const int inf = 987654321;
int n, m;
vector<int> dp, t;

// 引数: 今まででどの命令を既に実行したか
int rec(int mask) {
  if(mask == (1<<n) - 1) { return 0; }
  if(dp[mask] != inf) { return dp[mask]; }
  int used = 0; // 今まででどのメモリを既に使ったか
  for(int i=0; i<n; i++) {
    if(mask>>i & 1) { used |= t[i]; }
  }
  int res = inf;
  for(int i=0; i<n; i++) {
    if(mask>>i & 1) { continue; }
    int k = __builtin_popcount(t[i] & ~used); // t[i]にだけ立ってるビットを調べる
                                              // kが0のときも見に行かないといけない
    res = min(res, rec(mask | (1<<i)) + k*k); // i番目の命令をやる
  }
  return dp[mask] = res;
}

int OrderOfOperationsDiv2::
minTime(vector<string> s) {
  n = s.size(), m = s[0].size();
  t.assign(n, 0);
  for(int i=0; i<n; i++) {
    for(int j=0; j<m; j++) {
      t[i] |= (s[i][j] - '0') << j;
    }
  }
  dp.assign((1<<20) + 10, inf);
  return rec(0);
}

(ΦωΦ)＜再帰 解き方 その2 
#include <iostream>
#include <algorithm>
using namespace std;

class OrderOfOperationsDiv2 { public: int minTime(vector<string> s); };

const int inf = 987654321;
int n, m;
vector<int> dp, t;

// 引数: 今まででどのメモリを既に使ったか
int rec(int mask) {
  if(dp[mask] != inf) { return dp[mask]; }
  int res = inf;
  for(int i=0; i<n; i++) {
    int k = __builtin_popcount(t[i] & ~mask);
    if(k == 0) { continue; } // kが0のときはmask == (mask | t[i])なので見に行ってはいけない
    res = min(res, rec(mask | t[i]) + k*k); // i番目の命令をやる
  }
  if(res == inf) { res = 0; }
  return dp[mask] = res;
}

int OrderOfOperationsDiv2::
minTime(vector<string> s) {
  n = s.size(), m = s[0].size();
  t.assign(n, 0);
  for(int i=0; i<n; i++) {
    for(int j=0; j<m; j++) {
      t[i] |= (s[i][j] - '0') << j;
    }
  }
  dp.assign((1<<20) + 10, inf);
  return rec(0);
}

---
(ΦωΦ)＜for 解き方 その1
#include <iostream>
#include <algorithm>
using namespace std;

class OrderOfOperationsDiv2 { public: int minTime(vector<string> s); };

const int inf = 987654321;

int OrderOfOperationsDiv2::
minTime(vector<string> s) {
  int n = s.size(), m = s[0].size();
  vector<int> t(n);
  for(int i=0; i<n; i++) {
    for(int j=0; j<m; j++) {
      t[i] |= (s[i][j] - '0') << j;
    }
  }
  vector<int> dp(1<<n, inf);
  dp[0] = 0;
  for(int mask=0; mask<1<<n; mask++) {
    int used = 0;
    for(int i=0; i<n; i++) {
      if(mask>>i & 1) { used |= t[i]; }
    }
    for(int i=0; i<n; i++) {
      if(mask>>i & 1) { continue; }
      int k = __builtin_popcount(t[i] & ~used);
      dp[mask|(1<<i)] = min(dp[mask|(1<<i)], dp[mask]+k*k);
    }
  }
  return dp[(1<<n)-1];
}

(ΦωΦ)＜for 解き方 その2
#include <iostream>
#include <algorithm>
using namespace std;

class OrderOfOperationsDiv2 { public: int minTime(vector<string> s); };

const int inf = 987654321;

int OrderOfOperationsDiv2::
minTime(vector<string> s) {
  int n = s.size(), m = s[0].size();
  vector<int> t(n);
  int all = 0;
  for(int i=0; i<n; i++) {
    for(int j=0; j<m; j++) {
      t[i] |= (s[i][j] - '0') << j;
    }
    all |= t[i];
  }
  vector<int> dp(1<<m, inf);
  dp[0] = 0;
  for(int mask=0; mask<1<<m; mask++) {
    for(int i=0; i<n; i++) {
      int k = __builtin_popcount(t[i] & ~mask);
      dp[mask|t[i]] = min(dp[mask|t[i]], dp[mask]+k*k);
    }
  }
  return dp[all];
}

(ΦωΦ)＜おしまい