G6006 [GESP202403 六级] 好斗的牛 题解

知识点：状态压缩动态规划、排列、状态设计。

解题思路

状态dp[mask][i]表示已安排mask中的牛且最后一头为i时，最后位置的最小坐标。把未选牛j接在后面，增加max(b_i,a_j)+1。

为什么正确

给定排列时每对相邻牛只需取满足双方要求的最小间隔；枚举最后一头与新增牛覆盖所有排列，并保留最优前缀。

易错点

左右间隔要求不同；第一头位置为1，加入牛时必须检查mask中尚未选择。

复杂度

时间O(2^n n²)，空间O(2^n n)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<int>a(n),b(n);
    for(int &x:a)cin>>x;
    for(int &x:b)cin>>x;
    vector<vector<int>>dp(1<<n,vector<int>(n,1000000000));
    for(int i=0;i<n;i++)dp[1<<i][i]=1;
    for(int mask=1;mask<(1<<n);mask++)for(int i=0;i<n;i++)if(mask>>i&1)for(int j=0;j<n;j++)if(!(mask>>j&1))dp[mask|(1<<j)][j]=min(dp[mask|(1<<j)][j],dp[mask][i]+max(b[i],a[j])+1);
    cout<<*min_element(dp.back().begin(),dp.back().end());
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用16个自行生成的测试点。