c++ - 为什么 MCARDS 中需要前突变

Question

我试图在 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;
}

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

提前致谢

Answer 1

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

排列

假设我们有数字为 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 长度。 (t是卡片的数量)

在我们的例子中，最长的递增子序列是:

     0  1  2  3  4  5  6  7  8  9 10

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