Зачем нужны премутации в MCARDS
Я пытался решить проблему 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;
}
В чем логика перестановки в приведенном выше решении?
заранее спасибо
Решение
Эта проблема пытается найти самый дешевый способ перемещения карт, чтобы привести их в правильный порядок.
перестановка
Предположим, у нас есть красные, зеленые и синие карты с номерами от 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
Другие решения