首页 > 代码库 > 每天一道算法编程题(1)——网易笔试"工程师工作安排“问题
每天一道算法编程题(1)——网易笔试"工程师工作安排“问题
首先理解题目意思:每个人只能做工作序号表里的一件工作且两个人不能同时做一件工作。
AC思路:采用暴力枚举每种可能的分配方案,子问题的解决逐步向上解决了母问题,最终原问题得解。
标程作者:NotDeep(牛客网)
链接:https://www.nowcoder.com/discuss/22696?type=6&order=0&pos=5&page=2
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 vector<string> a; //a保存工作序号表 6 int n; 7 int b[10]; //标志数组b[i]用来记录编号为i的工作是否已经被分配,为0表示已分配,为1表示未分配 8 int ret; //记录分配计划数目 9 10 void dfs(int i) {//dfs[i]指当编号为0到i-1的人都已分配好工作时为编号为i到a.size()-1的人分配工作 11 if(i == a.size()) { 12 ret++; //一种分配方案结束 13 } else { 14 for(int j = 0; j < a[i].size(); j++) { 15 if(b[a[i][j] - ‘0‘]) { 16 b[a[i][j] - ‘0‘] = 0; 17 dfs(i + 1); 18 b[a[i][j] - ‘0‘] = 1; 19 } 20 } 21 } 22 } 23 24 int main() { 25 26 while(cin >> n) { 27 for(int i = 0; i < n; i++) { 28 string x; cin >> x; 29 a.push_back(x); 30 } 31 for(int i = 0; i < 10; i++) b[i] = 1; 32 ret = 0; 33 dfs(0); 34 cout << ret << endl; 35 } 36 return 0; 37 }
每天一道算法编程题(1)——网易笔试"工程师工作安排“问题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。