招商2021.9.16 c++第二题
2021.9.16招商银行c++第二题使用最小任务数覆盖所有app的题有人有想法吗？
是一个代码补空
题目描述：
数组req_apps:[app1,app2,app3,app4]为要求上线的apps
数组tasks为一个二维数组，tasks:[task1,task2,task3]
其中task1:[app1,app2]、task2:[app3,app4],task3:[app2,app3]
最少能覆盖所有req_apps中的任务数为2
有人能解释一下这个啥意思么，看不懂，太菜了#招商银行fintech##招商银行##笔经#
是一个代码补空
题目描述：
数组req_apps:[app1,app2,app3,app4]为要求上线的apps
数组tasks为一个二维数组，tasks:[task1,task2,task3]
其中task1:[app1,app2]、task2:[app3,app4],task3:[app2,app3]
最少能覆盖所有req_apps中的任务数为2
代码：
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int smallestTaskSet(vector<string> req_apps,vector<vector<string>> tasks)
{
//task_name_index装的是(app_i,i)
map<string,int> task_name_index;
int appsize=req_apps.size();
for(int i=0;i<appsize;++i)
{
task_name_index[req_apps[i]]=i;
}
vector<int> dp(1<<appsize,-1);
dp[0]=？;
for(int i=0;i<tasks.size();i++)
{
int current_task=0;
for(int j=0;j<tasks[i].size();j++)
{
int x=task_name_index[tasks[i][j]];
current_task？(1<<x);
}
for(int j=0;j<(1<<appsize);j++)
{
if(？)//当前集合计算过
{
int x=current_task|j;//更新的集合
if(dp[x]==-1||dp[x]>dp[j]+1)//集合没计算或者选最优
{
dp[x]=？;
}
}
}
}
return dp[1<<appsize-1];
}
int main()
{
return 0;
} 有人能解释一下这个啥意思么，看不懂，太菜了#招商银行fintech##招商银行##笔经#
查看11道真题和解析