1

我试图在http://www.spoj.com/problems/MCARDS/上解决关于 spoj 的 MCARDS 问题

我知道它涉及最长增加子序列逻辑，但经过多次尝试我没有找到这个问题的解决方案，所以我搜索解决方案，我找到以下解决方案：

int go (vector < int > &v) {
  int ans = 1;
    int n = v.size();
    vector < int > d(n, 1);
    for(int i = 1; i < n; ++i) {
        int mmax = -1;
        for(int j = 0; j < i; ++j) {
            if(v[j] < v[i] && (mmax == -1 || d[mmax] < d[j])) {
                mmax = j;
            }
        }
        if(mmax != -1) 
            d[i] += d[mmax];
        ans = max(ans, d[i]);
    }
    return ans;
}

int main () {
    int test_case;
#ifndef ONLINE_JUDGE
  IN("/home/tigran/Desktop/Debug/input.txt");
  OUT("/home/tigran/Desktop/Debug/output.txt");
  scanf("%d", &test_case);
#else
  test_case = 1;
#endif
    while(test_case--) {
        int c, n;
        scanf("%d%d", &c, &n);
        int t = n * c;
        vector < int > colors(t), values(t);
        for(int i = 0; i < t; ++i) {
            scanf("%d%d", &colors[i], &values[i]);
        }
        vector < int > ind;
        for(int i = 0; i < c; ++i) {
            ind.push_back(i);
        }
        int mmin = IINF;
        vector < int > v(t);
        do {
            int cnt = 0;
            for(int i = 0; i < c; ++i) {
                for(int j = 0; j < n; ++j) {
                    mat[ind[i]][j] = cnt++;
                }
            }
            for(int i = 0; i < t; ++i) {
                v[i] = mat[colors[i] - 1][values[i] - 1];
            }
            mmin = min(mmin, t - go(v));
        }while(next_permutation(ind.begin(), ind.end()));
        printf("%d\n", mmin);
    }
    return 0;
}

上述解决方案中排列背后的逻辑是什么？

提前致谢

4

1 回答 1

2

这个问题试图找到最便宜的移动卡片的方法，以使它们按正确的顺序排列。

排列

假设我们有数字 1 到 4 的红色、绿色和蓝色卡片。

所有相同的颜色必须在一起，并且在每个组内，必须对数字进行排序。

因此有 3!=3*2*1=6 可能的正确最终订单：

R1 R2 R3 R4 B1 B2 B3 B4 G1 G2 G3 G4  (RBG)
R1 R2 R3 R4 G1 G2 G3 G4 B1 B2 B3 B4  (RGB)
B1 B2 B3 B4 R1 R2 R3 R4 G1 G2 G3 G4  (BRG)
G1 G2 G3 G4 R1 R2 R3 R4 B1 B2 B3 B4  (GRB)
B1 B2 B3 B4 G1 G2 G3 G4 R1 R2 R3 R4  (BGR)
G1 G2 G3 G4 B1 B2 B3 B4 R1 R2 R3 R4  (GBR)

每个顺序由颜色的排列决定（显示在括号中）。

该解决方案通过迭代颜色的每个排列来工作。

对于每个排列，它在 v 中计算给定排列的每张卡片的正确位置。函数 go 用于计算将 v 放入排序顺序的最小移动次数。

例如，如果我们选择了排列 (RGB)，并且卡片原本是按顺序排列的：

R1 R2 R3 R4 G1 G2 G3 G4 B1 B2 B4 B3

那么 v 将被计算为

0  1  2  3  4  5  6  7  8  9  11 10

和 go 将确定需要一步来对卡片进行排序。

计数移动排序

go 函数通过计算 v 中最长的递增子序列来计算出最少的移动次数。

一旦我们找到了 LIS，我们就知道我们必须移动不在这个子序列中的每张牌，所以移动的次数是 LIS 的 t-length。（t是牌的数量）

在我们的示例中，最长的递增子序列将是：

     0  1  2  3  4  5  6  7  8  9 10

长度为 11，所以答案是 12-11=1

于 2014-06-13T06:24:31.550 回答