[AtCoder] ABC080 C – Shopping Street

問題

方針

ビット全探索

ある曜日のどの時間帯に店を営業するかどうかで利益が変わり、\( 5 \) つの曜日と午前・午後を考えれば良いので、\( 2^{10} \) 通りのビット全探索を行えば良いことが分かります。

店の営業情報は \( F_{i, j, k} \) と3つの添え字が使われていますが、便宜上 \( F_{i, j}\) として二次元配列で表すことにします。つまり、 \( j \) は \( 0 \leq j  \leq 9 \) の範囲で、曜日と時間帯の両方を表すことになります。
あとは、全ての通りについて利益を計算して最大値を求めます。注意すべきなのは、必ず一つ以上の時間帯で店が営業するという点です。

コード

提出したコード

利益の計算

  int profit = 0;
  // cnt: 両方が営業している時間帯の個数
  for (int i = 0; i < N; i++) {
    int cnt = 0;
    for (int j = 0; j < 10; j++) {
      if(F[i][j] == 1 && bit[j] == 1) cnt++;
    }
    profit += P[i][cnt];
  }

 

AtCoder,ビット全探索,探索

Posted by ヤマカサ