Зачем нужны премутации в MCARDS

Question

Я пытался решить проблему MCARDS на спой в http://www.spoj.com/problems/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, мы знаем, что должны переместить каждую карту, которая не входит в эту подпоследовательность, и поэтому число ходов равно t-длине LIS. (т это количество карт)

В нашем примере самая длинная увеличивающаяся подпоследовательность будет:

     0  1  2  3  4  5  6  7  8  9 10

который имеет длину 11, так что ответ 12-11=1