引言全排列、双任务最优分配、网格连通块DFS 排列回溯型 DFS标记复用、状态撤销子集枚举 DFS最优性剪枝网格连通 DFS图遍历 题意额外条件洛谷P1706全排列P2392DFS子集枚举 P1331DFS连通块文章目录全排列涉及DFS 回溯算法标记 撤销标记解题过程实现代码临时抱佛脚涉及**DFS 子集枚举** **最优性剪枝**解题过程实现代码海战涉及网格连通块 DFS解题过程关键剪枝代码实现全排列P1706 全排列问题 - 洛谷涉及DFS 回溯算法标记 撤销标记这个题目在写的时候忘记保留5个场宽了coutsetw(5)ans[i];就是简单的全排列数跟第三场萌新赛题的G题类似的过程G题入口但是比G题要简单 G比这道题多了一部分的限制条件解题过程直接把步数step放入DFS中 去直接搜 将寻找过的数 标记用过 避免重复统计跑完一遍DFS后记得把标记回溯释放 以便下一轮DFS使用数据DFS的出口就定为步数step要排列出的数n刚写完代码的时候忘记清空ans数组了ans.pop_back();实现代码#includebits/stdc.h#includeiomanip#definelllonglong#defineendl\n#defineIOSios::sync_with_stdio(0),cin.tie(0),cout.tie(0);#defineullunsignedlonglong#definefifirst#definesesecond#defineYEScoutYESendl;#defineNOcoutNOendl;usingnamespacestd;ll n;boolvis[10];vectorllans;voiddfs(ll step){if(stepn){for(ll i0;ians.size();i){coutsetw(5)ans[i];}coutendl;return;}for(ll i1;in;i){if(vis[i]){continue;}vis[i]true;ans.push_back(i);dfs(step1);ans.pop_back();vis[i]false;}}intmain(){IOS cinn;dfs(0);// coutfixedsetprecision(x) ;return0;}临时抱佛脚P2392 kkksc03 考前临时抱佛脚 - 洛谷涉及DFS 子集枚举最优性剪枝解题过程每科独立求解各科时间累加。DFS step当前第几道题目left左脑累计时间right右脑累计时间。最优性剪枝如果当前max(left,right) ansmin后续分支不可能得到更优解直接 return 剪掉整棵子树。递归出口step tim.size()所有题目分配完毕更新该科最小时间。solve 函数处理单科目4 次调用累加答案voiddfs(ll step,ll left,ll right,vectorlltim,llansmin){if(max(left,right)ansmin){return;}if(steptim.size()){ansminmin(ansmin,max(left,right));return;}dfs(step1,lefttim[step],right,tim,ansmin);dfs(step1,left,righttim[step],tim,ansmin);}实现代码#includebits/stdc.h#includeiomanip#definelllonglong#defineendl\n#defineIOSios::sync_with_stdio(0),cin.tie(0),cout.tie(0);#defineullunsignedlonglong#definefifirst#definesesecond#defineYEScoutYESendl;#defineNOcoutNOendl;usingnamespacestd;ll n;voiddfs(ll step,ll left,ll right,vectorlltim,llansmin){if(max(left,right)ansmin){return;}if(steptim.size()){ansminmin(ansmin,max(left,right));return;}dfs(step1,lefttim[step],right,tim,ansmin);dfs(step1,left,righttim[step],tim,ansmin);}llsolve(ll s){vectorlltim(s);for(ll i0;is;i){cintim[i];}ll ansmin1e18;dfs(0,0,0,tim,ansmin);returnansmin;}intmain(){IOS ll ans0;ll s1,s2,s3,s4;cins1s2s3s4;anssolve(s1);anssolve(s2);anssolve(s3);anssolve(s4);coutansendl;// coutfixedsetprecision(x) ;return0;}海战P1331 海战 - 洛谷涉及网格连通块 DFS这道题跟专题1里面的力扣200岛屿数量力扣200入口是相同的思路 主要是多了一些剪枝条件解题过程关键剪枝第一次写的时候忘记这个条件限制直接WA了详细情况如图所示代码实现#includebits/stdc.h#includeiomanip#definelllonglong#defineendl\n#defineIOSios::sync_with_stdio(0),cin.tie(0),cout.tie(0);#defineullunsignedlonglong#definefifirst#definesesecond#defineYEScoutYESendl;#defineNOcoutNOendl;usingnamespacestd;ll m,n;charg[1005][1005];ll dx[4]{-1,1,0,0};ll dy[4]{0,0,-1,1};boolvis[1005][1005];voiddfs(ll x,ll y){vis[x][y]true;for(ll i0;i4;i){ll nxxdx[i];ll nyydy[i];if(nx0nxmny0nyn!vis[nx][ny]g[nx][ny]#){dfs(nx,ny);}}}intmain(){IOS cinmn;boolbadfalse;for(ll i0;im;i){cing[i];}for(ll i0;i1m;i){for(ll j0;j1n;j){ll c0;if(g[i][j]#){c;}if(g[i1][j]#){c;}if(g[i][j1]#){c;}if(g[i1][j1]#){c;}if(c3){badtrue;}}}if(bad){coutBad placement.endl;return0;}ll cnt0;memset(vis,0,sizeof(vis));for(ll i0;im;i){for(ll j0;jn;j){if(g[i][j]#!vis[i][j]){cnt;dfs(i,j);}}}coutThere are cnt ships.endl;// coutfixedsetprecision(x) ;return0;}