読者です 読者をやめる 読者になる 読者になる

SRM 667 Div2 Medium OrderOfOperationsDiv2

問題

SRM 667 - TopCoder Wiki

ある計算機を実行する時の最小の実行時間を求める問題. 命令はn個あり,s[i][j]はi番目の命令がj番目のメモリを使うことを意味する. メモリはキャッシュすることが出来,命令iの実行時間はキャッシュされていないメモリの個数の2乗かかる. 命令の実行順序に制限はない.

解答

メモリの個数は高々20なので高々1<<20の状態を保持して,全状態から各命令を実行した時の時間を計算し,最小時間を記憶する.

class OrderOfOperationsDiv2
{
public:
  int minTime(vector <string> s)
    {
      int n = s.size();
      int m = s[0].size();
      int inf = 10000000;
      vector<int> dp(1 << m, inf);
      dp[0] = 0;
      int res_state = 0;
      vector<int> mask(n, 0);
      int i, j;
      for(i = 0; i < n; i++){
        for(j = 0; j < m; j++){
          if (s[i][j] == '1'){
            mask[i] |= (1 << j );
            res_state |= (1 << j );
          }
        }
      }

      for(int i = 0; i < (1 << m); i++){
          // cout << "i=" << i << " (1 << m)=" << (1 << m) << endl;
        for(int j = 0; j < n; j++){
          int uni = mask[j] | i;
          int uncached = uni - i;
          int num_uncached = 0;
          for(int k = 0; k < m; k++) if (1&(uncached >> k)){
            num_uncached++;
          }
          // cout << "uncached=" << uncached << " num_uncached=" << num_uncached;
          // cout << "uni=" << uni << endl;
          dp[uni] = min(dp[uni], dp[i] + num_uncached * num_uncached);
          // if (dp[uni]==inf) dp[uni] = num_uncached * num_uncached;
          // cout << " i=" << i << " mask[" << j << "]="
          //      << mask[j]
          //      << " dp[" << uni << "]=" << dp[uni]<< endl;
        }
      }
      return dp[res_state];
    }
};