深搜全排列与函数全排列取最大值

深搜全排列

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e3+10;
ll a[N],b[N],n;
ll ans = 1e9;
ll s[10];
bool vis[10];
//对牛的排列情况进行全排列(也就是暴力判断所有可能性)
//例如 只有三头牛
//那只有 （牛1 牛2 牛3）（牛1 牛3 牛2）（牛2 牛1 牛3）（牛2 牛3 牛1）（牛3 牛1 牛2） （牛3 牛2 牛1）排列方式
//接着通过程序把这些排列可能性所对应的牛棚数结果取最小值就是答案 

void dfs(ll idx)//idx 当前准备选择一个牛放置在idx的位置（是排列中的位置）
{
    if(idx == n+1)//已经到第n+1位置，说明前n个位置放好了牛，也就是这个排列情况已确定可以进行计算所需要的牛棚数了
    {
        ll sum = 1;//第一头牛需要一个棚，所以开局所需要的牛棚数是1  第一只牛放在1的位置 占一个牛棚
        for(int i = 2;i<=n;i++)//接着只需要搞定后续的2-n头牛   i 是 排列中第几个位置  s[i] 是这个位置对应的牛
            sum+=max(b[s[i-1]],a[s[i]])+1;
            //max(b[s[i-1]],a[s[i]]) 第i-1位置的牛和i位置的牛所需要间隔的牛棚数 
            //b[s[i-1]为前一头牛往后的肘击距离 a[s[i]]为后一头牛向前的肘击距离 他们不能肘到，所以取最大值
           //最后+1是因为第s[i]这头牛放置也需要一个牛棚，前面算的是需要间隔的牛棚数
       
        ans = min(ans,sum);//遍历结束 当前排列情况答案和最小值比较
    }
    for(int i = 1;i<=n;i++)//遍历 1 - n头牛
    {
        if(!vis[i])//如果当前这个牛没用过
        {
            s[idx] = i;//在第idx个位置(排列中的位置)放置第i头牛
            vis[i] = 1; // 标记第i头牛用过
            dfs(idx+1); // 以idx位置选择第i头牛进行深搜，将第idx位置选择第i头牛的所有可能性深搜完了。
            vis[i] = 0; //根据上行注释，当前选择第i头牛的情况全部都搞定了，就准备这个位置不再选第i头牛，而去判断这个位置
                           //选其他的牛的可能性，所以要给"解锁"，让第i头牛标记成没用过。
        }
    }
}
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;
}

函数全排列
核心逻辑和上面一致，只不过把使用深搜全排列直接改成使用next_permutation函数全排列

#include <algorithm>
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e3+10;
ll a[N],b[N],n;
ll ans = 1e9;
ll s[10];
int main()
{
    cin>>n;
    for(int i = 1;i<=n;i++)
        s[i] = i;
    for(int i = 1;i<=n;i++)
        cin>>a[i];
    for(int i = 1;i<=n;i++)
        cin>>b[i];
    do{
        ll sum = 1;
        for(int i = 2;i<=n;i++)
            sum+=max(b[s[i-1]],a[s[i]])+1;
        ans = min(ans,sum);
    }while(next_permutation(s****+n+1));
    cout<<ans;
}