洛谷 P10377：[GESP202403 六级] 好斗的牛 ← dfs

【题目来源】https://www.luogu.com.cn/problem/P10377【题目描述】你有 10^9 个牛棚从左到右一字排开。你希望把 n 头牛安置到牛棚里。麻烦的是你的牛很好斗如果他们附近有其他的牛他们就会不安分地去挑事。其中第 i 头牛的攻击范围是 (ai,bi)这意味着如果他的左边 ai 个牛棚或者右边 bi 个牛棚有其他牛它就会去挑事。你想留下一段连续的牛棚并把其他牛棚都卖掉。请问您最少需要留下多少牛棚才能保证至少存在一种方案能够把所有的 n 头牛都安置进剩余的牛棚里且没有牛会挑事【输入格式】第一行一个正整数 n。第二行 n 个正整数 a1a2….an。第三行 n 个正整数 b1b2….bn。​​​​​​​【输出格式】输出一行一个整数表示答案。​​​​​​​【输入样例】31 2 33 2 1【输出样例】7【数据范围】对 20% 的数据保证 n2。另有 20% 的数据保证 n3。对 80% 的数据保证 n≤8。对于所有的测试数据保证1≤n≤91≤ai,bi≤10^3。【算法分析】n≤9最多 9! 362880 种排列DFS 回溯完全可以轻松跑完。【算法代码】#include bits/stdc.h using namespace std; const int N10; int a[N],b[N]; bool st[N]; int n,ans; void dfs(int cnt,int pre,int pre_pos) { if(cntn) { if(pre_pos1ans) anspre_pos1; return; } for(int i1; in; i) { if(!st[i]) { st[i]true; int gapmax(b[pre],a[i]); int cur_pospre_posgap1; dfs(cnt1,i,cur_pos); st[i]false; } } } int main() { cinn; for(int i1; in; i) cina[i]; for(int i1; in; i) cinb[i]; ansINT_MAX; for(int i1; in; i) { st[i]true; dfs(1,i,0); st[i]false; } coutansendl; return 0; } /* in: 3 1 2 3 3 2 1 out: 7 */【参考文献】https://gesp.ccf.org.cn/101/attach/1602047203868704.pdf