cafelier@SRM

SRM469 500

あとで | 17:27 |

• 余計な引き算を消しただけ

class TheMoviesLevelTwoDivOne { public:
   vector <int> find(vector <int> length, vector <int> scary) 
   {
      int N = length.size();

      vector<int> lwb(N), inc(N);
      // 寝ないで見終えられる下限
      for(int i=0; i<N; ++i)
         if( scary[i]+47 < length[i] )
            lwb[i] = length[i] - 47;
         else
            lwb[i] = scary[i];
      // 見終わったときの増分
      for(int i=0; i<N; ++i)
         inc[i] = 47 - length[i];

      // メモ化再帰
      memo = vector<bool>(1<<N);
      memo[(1<<N)-1] = true;
      vector<int> temp;
      rec(0, 74, N, lwb, inc, temp);

      // 最適解の後ろに見てない映画を辞書順最小に並べる
      set<int> not_used;
      for(int i=0; i<N; ++i) not_used.insert(i);
      for(int i=0; i<result.size(); ++i)
         not_used.erase(result[i]);
      result.insert(result.end(), not_used.begin(), not_used.end());

      // 以上
      return result;
   }

   vector<int>  result;
   vector<bool> memo;
   void rec(int mask, int cur, int N, vector<int>& lwb, vector<int>& inc, vector<int>& temp)
   {
      if( result.size() < temp.size() )
         result = temp;
      if( memo[mask] )
         return;
      memo[mask] = true;

      for(int i=0; i<N; ++i)
         if( !(mask & (1<<i)) && cur>=lwb[i] )
         {
            temp.push_back(i);
            rec(mask|(1<<i), cur+inc[i], N, lwb, inc, temp);
            temp.pop_back();
         }
   }
};