企业官网建设流程全解析

【题目来源】
https://www.luogu.com.cn/problem/P10377

【题目描述】
你有 10^9 个牛棚，从左到右一字排开。你希望把 n 头牛安置到牛棚里。麻烦的是，你的牛很好斗，如果他们附近有其他的牛，他们就会不安分地去挑事。其中，第 i 头牛的攻击范围是 (ai,bi)，这意味着，如果他的左边 ai 个牛棚或者右边 bi 个牛棚有其他牛，它就会去挑事。
你想留下一段连续的牛棚，并把其他牛棚都卖掉。请问您最少需要留下多少牛棚，才能保证至少存在一种方案能够把所有的 n 头牛都安置进剩余的牛棚里，且没有牛会挑事？

【输入格式】
第一行一个正整数 n。
第二行 n 个正整数 a1，a2，….，an。
第三行 n 个正整数 b1，b2，….，bn。​​​​​​​

【输出格式】
输出一行一个整数表示答案。​​​​​​​

【输入样例】
3
1 2 3
3 2 1

【输出样例】
7

【数据范围】
对 20% 的数据，保证 n=2。
另有 20% 的数据，保证 n=3。
对 80% 的数据，保证 n≤8。
对于所有的测试数据，保证1≤n≤9，1≤ai,bi≤10^3。

【算法分析】
n≤9，最多 9! = 362880 种排列，DFS 回溯完全可以轻松跑完。

【算法代码】

#include <bits/stdc++.h> using namespace std; const int N=10; int a[N],b[N]; bool st[N]; int n,ans; void dfs(int cnt,int pre,int pre_pos) { if(cnt==n) { if(pre_pos+1<ans) ans=pre_pos+1; return; } for(int i=1; i<=n; i++) { if(!st[i]) { st[i]=true; int gap=max(b[pre],a[i]); int cur_pos=pre_pos+gap+1; dfs(cnt+1,i,cur_pos); st[i]=false; } } } int main() { cin>>n; for(int i=1; i<=n; i++) cin>>a[i]; for(int i=1; i<=n; i++) cin>>b[i]; ans=INT_MAX; for(int i=1; i<=n; i++) { st[i]=true; dfs(1,i,0); st[i]=false; } cout<<ans<<endl; return 0; } /* in: 3 1 2 3 3 2 1 out: 7 */

【参考文献】
https://gesp.ccf.org.cn/101/attach/1602047203868704.pdf