当前位置: 首页 > 工具软件 > Flip! > 使用案例 >

Swap and Flip

狄宗清
2023-12-01

题意

n n n张卡牌,每张卡牌的正面是数字 a a a ,背面是数字 b b b。操作:交换相邻的两张卡牌,然后翻转。问最少需要多少次操作使得卡牌朝上的数字组成非递减数列?

( n < = 18 n <= 18 n<=18, 1 < = a , b < = 50 1 <= a, b <=50 1<=a,b<=50)

题解

n n n比较小,不是DFS就是状压DP

首先,多动笔会发现:同一张卡牌被交换奇数次后,卡牌的背面朝上,如果是偶数次,卡牌的正面朝上

然后,枚举有哪些位置的卡牌在**最终状态(朝上的数字构成非递减数列)**是被翻转过的。比如, i i i 位置的卡牌被标记为1,表示第 i i i 张卡牌在最终状态是背面朝上的(交换了奇数次);如果是0,则正面朝上(交换了偶数次)。

通过枚举,我们可以推出最终状态,所以我们仅仅需要完成两个工作:①能否匹配 ②正确计算逆序对

  • 匹配:假设第 i i i 张卡牌被标记为1,它在最终状态中的位置为 j j j。如果 ∣ i − j ∣ % 2 = = 1 | i - j| \% 2 ==1 ij%2==1,说明这张卡牌移动了奇数次,否则,说明推出的最终状态不成立;此处的难点在于:如果碰到相同的数字,既最终状态有多个位置上的数字与 b i b_i bi相同,怎么确定是否匹配?贪心,既找到满足 ∣ i − j ∣ % 2 = = 1 | i - j| \% 2 ==1 ij%2==1的位置为止。

    贪心的正确性不会证,难受 ≧ ﹏ ≦

    // tp: 最终状态
    // id: 第 i 张卡牌的初始位置,朝上的数字是 x
    bool check(vector<int> &tp, int id, int x, int is_b) {
        bool flag = false;
        myfor(i, 0, n) if (!vis[i] && (x == tp[i]) && ((abs(id - i) & 1) == is_b)) {
            vis[i] = 1;
            ind[id] = i;
            return true;
        }
        return false;
    }
  • 计算逆序对:用 i n d ind ind数组标记第 i i i张卡牌在最终状态的位置,然后求 i n d ind ind的逆序对.

复杂度 O ( 2 n n 2 ) O(2^n n^2) O(2nn2)


#define myfor(i, a, b) for (int i = a; i < b; ++i)

const int INF = 0x3f3f3f3f;

int n;
int a[20], b[20], ind[20];

bool vis[20];

bool check(vector<int> &tp, int id, int x, int is_b) {
    bool flag = false;
    myfor(i, 0, n) if (!vis[i] && (x == tp[i]) && ((abs(id - i) & 1) == is_b)) {
        vis[i] = 1;
        ind[id] = i;
        return true;
    }
    return false;
}

int cal_invesion_number() {
    int cnt = 0;
    myfor(i, 0, n) {
        for (int j = n - 1; j > i; j--) if (ind[j] < ind[j - 1]) {
            cnt++;
            swap(ind[j], ind[j - 1]);
        }
    }
    return cnt;
}

int main()
{
    cin >> n;
    myfor(i, 1, n + 1) cin >> a[i];
    myfor(i, 1, n + 1) cin >> b[i];

    int ans = INF;
    myfor(i, 0, (1 << n)) {

        bool flag = true;
        vector<int> tp;

        myfor (j, 0, n) {
            if ((i >> (n - j - 1)) & 1) tp.pb(b[j + 1]);
            else tp.pb(a[j + 1]);
        }
        sort(tp.begin(), tp.end());

        myfor(j, 0, n) {
            int is_b = (i >> (n - j - 1)) & 1;
            int x = is_b ? b[j + 1] : a[j + 1];
            if (!check(tp, j, x, is_b)){
                flag = false;
                break;
            }
        }

        if (flag) ans = min(ans, cal_invesion_number());

        memset(vis, 0, sizeof(vis));
        memset(ind, 0, sizeof(ind));
    }

    cout << ((ans == INF) ? -1 : ans) << endl;
    return 0;
}

 类似资料:

相关阅读

相关文章

相关问答