LeetCode Weekly Contest 145
問題文
省略
省略
#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)