LeetCode Weekly Contest 145 4問目 - Smallest Sufficient Team [1125]

Source

LeetCode Weekly Contest 145
問題文

問題概要

省略

解法

省略

cLayversion 20190714-1)のコード [C++に変換後]

#include<bits/stdc++.h>
using namespace std;
int dp[100000];
int back[100000];
int ls[100000];
class Solution{
  public:
  vector<int> smallestSufficientTeam(vector<string>& skills, vector<vector<string>>& people){
    int N, S, i, j, k, mask[60];
    vector<int> res;
    S = skills.size();
    N = people.size();
    for(i=0;i<N;i++){
      mask[i] = 0;
      for(j=0;j<people[i].size();j++){
        for(k=0;k<S;k++){
          if(skills[k] == people[i][j]){
            mask[i] |= (1<<k);
          }
        }
      }
    }
    for(i=0;i<1<<S;i++){
      dp[i] = 1073709056;
    }
    dp[0] = 0;
    for(i=0;i<1<<S;i++){
      for(j=0;j<N;j++){
        k = (i|mask[j]);
        if(dp[k] > dp[i]+1){
          dp[k] = dp[i] + 1;
          back[k] = i;
          ls[k] = j;
        }
      }
    }
    i = (1<<S)-1;
    while(i){
      res.push_back(ls[i]);
      i = back[i];
    }
    return res;
  }
}
;

// cLay varsion 20190714-1

// --- original code ---
// int dp[1d5], back[1d5], ls[1d5];
// 
// class Solution {
// public:
//   vector<int> smallestSufficientTeam(vector<string>& skills, vector<vector<string>>& people) {
//     int i, j, k;
//     int mask[60];
//     int S, N;
//     vector<int> res;
// 
//     S = skills.size();
//     N = people.size();
// 
//     rep(i,N){
//       mask[i] = 0;
//       rep(j,people[i].size()){
//         rep(k,S) if(skills[k] == people[i][j]) mask[i] |= (1<<k);
//       }
//     }
// 
//     rep(i,1<<S) dp[i] = int_inf;
//     dp[0] = 0;
//     rep(i,1<<S) rep(j,N){
//       k = (i|mask[j]);
//       if(dp[k] > dp[i]+1){
//         dp[k] = dp[i] + 1;
//         back[k] = i;
//         ls[k] = j;
//       }
//     }
// 
//     i = (1<<S)-1;
//     while(i){
//       res.push_back(ls[i]);
//       i = back[i];
//     }
// 
//     return res;
//   }
// };
// 
// {
//   // main関数を適当に処理する
// }

Current time: 2024年03月29日10時58分07秒
Last modified: 2019年07月14日13時57分06秒 (by laycrs)
Tags: Competitive_Programming_Incomplete LeetCode
トップページに戻る

Logged in as: unknown user (not login)

ログイン: