Я пытался решить эту проблему конкурса найма (сейчас закрыт) * 1001 *
Лексикографические строки
Вам дана матрица символов. В одну операцию вы можете удалить
столбец матрицы. Вы можете выполнить столько операций, сколько вам
хочу. Ваша задача - сделать итоговую матрицу интересной, т.е.
строка, образованная символами строки, лексикографически меньше
или равно строке, образованной символами строки. Тебе нужно
использовать минимально возможное количество операций. Пустая матрица
всегда интересная матрица.
Input
Первая строка содержит два целых числа и. Следующие строки содержат
буквы каждая.
выход
В выводе вам нужно вывести минимальное количество операций для
сделать матрицу интересной.
Препятствия
В качестве символов на входе используются только строчные буквы английского алфавита.
Пример ввода
3 3
CFG
АГК
ДЛМ
Пример вывода
1
Объяснение
Удалите первый столбец, чтобы сделать матрицу интересной.
Я почти уверен, что это проблема DP. У меня были трудности с поиском оптимальной подзадачи, хотя. Мне удалось пройти всего пару тестовых случаев
Я определил dp[i][j] как минимальное количество столбцов, которые нужно удалить, чтобы получить интересную матрицу.
И для каждого персонажа input[i][j] есть две возможности.
- если предыдущая запись лексикографически действительна, мы можем взять
dp[i][j - 1] и текущий ввод ничего не изменит.
- иначе мы проверяем, если
input[i -1][j] и input[i][j], если они в правильном порядке, мы считаем dp[i][j - 1], иначе этот столбец также недопустим, поэтому мы добавляем 1 к dp[i][j-1]
Мой Солнц. код
int n, m;
cin >> n >> m;
vector<string> input(n);
for (int i = 0; i < n; ++i) {
string temp = "";
for (int j = 0; j < m; ++j) {
char c;
cin >> c;
temp = temp + c;
}
input[i] = temp;
}
vector<vector<int> > dp(n, vector<int>(m, 0));
for (int i = 1; i < n; ++i) {
for (int j = 1; j < m; ++j) {
//Left is valid
if (input[i - 1][j - 1] < input[i][j - 1]) {
dp[i][j] = dp[i][j - 1];
}
else {
//Current is valid
if (input[i - 1][j] <= input[i][j]) {
dp[i][j] = dp[i][j - 1];
}
else {
dp[i][j] = dp[i][j - 1] + 1;
}
}
}
}
cout << dp[n - 1][m - 1] << endl;