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

【题目链接】

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

【题目考点】

1. 深搜

【解题思路】

解法1：枚举全排列

将所有牛放入牛棚后，就会形成一个牛的编号的排列。
如果相邻的两头牛，坐标是编号为i的牛，右边是编号为j的牛，那么第i号牛右侧$b_i$个牛棚不能有牛，第j号牛左侧$a_j$个牛棚不能有牛，这两头牛之间空牛棚的最小的长度为$max(b_i,a_j)$。
对于每种牛编号的排列，相邻的两头牛之间的空牛棚的长度都取最小长度，那么对于每种牛的排列，都存在一个最小的总牛棚长度len，能够把所有的 n 头牛都安置牛棚里。在这种情况下，如果第1头牛安置在1号牛棚，那么第n号牛就安置在第len号牛棚。
枚举所有牛的排列，求出每种排列下的最小总牛棚长度len，比较得到最小值，即为结果。
题目给定，牛的数量n最大值为9，9个不同元素的全排列数量为$9!=362880$，枚举9个元素的全排列是可行的，不会超时。

枚举全排列可以通过深搜完成，也可以调用STL函数next_permutation完成。

解法2：搜索

搜索就是有一定目的的枚举，
每层搜索确定第k个放入牛棚的牛的第几号牛，记录上一次选择的牛所在的牛棚lastPos，和上一次选择的牛的编号lastCow，

• 如果当前是第一个放入牛棚的牛，则将它放在1号牛棚。
• 如果不是第一个放入牛棚的牛，假设这一次选择第i号牛放入牛棚，那么lastPos右侧max(b[lastCow], a[i])个牛棚必须的空牛棚，其下一个牛棚才可以放牛。第i号牛能放的编号最小的牛棚为lastPos+max(b[lastCow], a[i])+1。

当放完n头牛后，第n头牛所在的牛棚编号即为当前牛的排列所能得到的最小牛棚长度len。使用len更新ans，求最小值。最后ans即为结果。

【题解代码】

解法1：枚举全排列

• 写法1：深搜

#include<bits/stdc++.h>
using namespace std;
#define N 15
int n, a[N], b[N], cow[N], ans = 1e9;
bool vis[N];//vis[i]：是否已把第i头牛放在牛棚中 
void dfs(int k)//确定第k头牛
{
	if(k > n)
	{
		int len = 1;//最小牛棚长度，第1号牛占据1号牛棚，初始长度为1 
		for(int i = 2; i <= n; ++i)
			len += max(b[cow[i-1]], a[cow[i]])+1;//第i-1个牛和第i个牛之间空牛棚长度为 max(b[i-1], a[i])，再加上第i头牛占据1个牛棚 
		ans = min(ans, len);
		return; 
	}
	for(int i = 1; i <= n; ++i) if(!vis[i])
	{
		vis[i] = true;
		cow[k] = i;//cow：记录牛的排列 
		dfs(k+1);
		vis[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];
	dfs(1);
	cout << ans; 
	return 0;
}

• 写法2：使用STL函数：next_permutaion求下一个排列

#include<bits/stdc++.h>
using namespace std;
#define N 15
int n, a[N], b[N], cow[N], ans = 1e9;
int main()
{
	cin >> n;
	for(int i = 1; i <= n; ++i)
		cin >> a[i];
	for(int i = 1; i <= n; ++i)
		cin >> b[i];
	for(int i = 1; i <= n; ++i)
		cow[i] = i;//cow：记录牛的排列，初始排列为字典序最小排列：1~n 
	do
	{
		int len = 1;//最小牛棚长度，第1号牛占据1号牛棚，初始长度为1 
		for(int i = 2; i <= n; ++i)
			len += max(b[cow[i-1]], a[cow[i]])+1;//第i-1个牛和第i个牛之间空牛棚长度为 max(b[i-1], a[i])，再加上第i头牛占据1个牛棚 
		ans = min(ans, len);	
	} while(next_permutation(cow+1, cow+1+n));//取cow[1]~cow[n]的下一个排列
	cout << ans; 
	return 0;
}

解法2：深搜

#include<bits/stdc++.h>
using namespace std;
#define N 15
int n, a[N], b[N], ans = 1e9;
bool vis[N];//vis[i]：是否已把第i头牛放在牛棚中 
//确定第k个放入牛棚的牛 lastCow：上一头放入牛棚的牛的编号 lastPos：上一次放入牛棚的牛所在牛棚 
void dfs(int k, int lastCow, int lastPos)
{
	if(k > n)
	{
		ans = min(ans, lastPos);
		return;
	}
	if(lastPos > ans)//剪枝：如果当前使用的牛棚长度大于已求出的结果，就不再搜索 
		return;
	for(int i = 1; i <= n; ++i) if(!vis[i])
	{
		vis[i] = true;
		if(k == 1)
			dfs(k+1, i, 1);//如果是第1头牛，一定放入1号牛棚 
		else
			dfs(k+1, i, lastPos+max(b[lastCow], a[i])+1);//如果不是第1头牛，那么第k头牛放所在牛棚的位置：上一头牛的位置l+中间空牛棚的长度+1 
		vis[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];
	dfs(1, 0, 0);
	cout << ans; 
	return 0;
}