Задача с сайта e-olymp.com.
Условие задачи
Имеется строка [latex]s[/latex]. Разрешается взять два любых одинаковых соседних символа и удалить их из строки. Эту операцию можно производить пока имеется возможность. Сначала Вы можете выбрать любое количество символов в строке и удалить их. Определить наименьшее количество символов, которое Вы можете удалить сначала так, чтобы затем выполняя разрешенную операцию, получить пустую строку.
Входные данные
Содержит строку [latex]s[/latex] ([latex]1 ≤[/latex] длина[latex]\left( s \right) [/latex] [latex]≤ 100)[/latex].
Выходные данные
Вывести наименьшее количество символов, которое следует удалить сначала.
Тесты
| № | Входные данные | Выходные данные |
| 1 | abbcddka | 2 |
| 2 | ABBA | 0 |
| 3 | abcde | 5 |
| 4 | abbac | 1 |
Код на C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
#include <iostream> #include <string> using namespace std; int **answers; string s; int calculate(int l, int r){ if(l > r) return 0; //Если индекс левой границы отрезка больше индекса правой. if(answers[l][r] == -1){ //Если ответ для данного отрезка ещё не известен, находим его. answers[l][r] = s.size(); if(s[l] == s[r]) answers[l][r] = min(answers[l][r], calculate(l+1, r-1)); for(int i = l; i < r; ++i){ answers[l][r] = min(answers[l][r], calculate(l, i) + calculate(i+1, r)); } } return answers[l][r]; } int main() { getline(cin, s); //Ввод строки. answers = new int*[s.size()]; for(int i = 0; i < s.size(); ++i){ answers[i] = new int[s.size()]; } //Заполнение массива начальными значениями. for(int i = 0; i < s.size(); ++i){ for(int j = 0; j <= s.size(); ++j){ if(i == j) answers[i][j] = 1; else answers[i][j] = -1; } } //Вывод ответа. cout<<calculate(0, s.size()-1); return 0; } |
Код на Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
import java.util.*; class Main { static int[][] answers; static String s; static int calculate(int l, int r){ if(l > r) return 0; //Если индекс левой границы отрезка больше индекса правой. if(answers[l][r] == -1){ //Если ответ для данного отрезка ещё не известен, находим его. answers[l][r] = s.length(); if(s.charAt(l) == s.charAt(r)) answers[l][r] = Math.min(answers[l][r], calculate(l+1, r-1)); for(int i = l; i < r; ++i){ answers[l][r] = Math.min(answers[l][r], calculate(l, i) + calculate(i+1, r)); } } return answers[l][r]; } public static void main (String[] args) throws java.lang.Exception { Scanner in = new Scanner(System.in); s = in.nextLine(); //Ввод строки. answers = new int[s.length()][s.length()]; //Заполнение массива начальными значениями. for(int i = 0; i < s.length(); ++i){ for(int j = 0; j < s.length(); ++j){ if(i == j) answers[i][j] = 1; else answers[i][j] = -1; } } //Вывод ответа. System.out.print(calculate(0, s.length()-1)); } } |
Описание
Идея решения состоит в том, чтобы разбить строку на меньшие по длине подстроки и найти ответ на задачу для каждой из них. Для хранения строки используется переменная s, а ответы на подзадачи содержатся в двумерном массиве целых чисел answers. В answers[i][j] находится ответ для подстроки с i-ого по j-й символ включительно. В функции main сначала вводится строка s. Далее ширина и глубина массива answers устанавливаются равными длине s. После этого он заполняется начальными значениями. Значение [latex]-1[/latex] означает, что ответ для этой ячейки ещё не был найден. Однако очевидно, что если строка состоит ровно из одного символа, согласно условию задачи, его придётся удалить, значит, главную диагональ можно сразу заполнить единицами. Затем происходит вызов рекурсивной функции calculate, принимающей индексы левой и правой границ целевой подстроки. Первый раз она вызывается для всей строки от первого до последнего символа. Работает эта функция следующим образом: если индекс левой границы отрезка больше индекса правой, что, в случае данной задачи, не имеет смысла, она возвращает ноль. Иначе она возвращает ответ на задачу для данной подстроки, а если этого не делалось ранее, то предварительно находит его. Происходит это так: сначала значение ответа устанавливается равным длине подстроки, поскольку в худшем случае необходимо будет удалить её всю целиком. Если символы на концах подстроки одинаковые, они, как сказано в условии, будут удалены в дальнейшем, потому нужно рассматривать минимум из текущего значения ответа и ответа для подстроки без крайних символов. Однако может оказаться, что выгоднее удалить символы из каких-то двух меньших подстрок, потому далее в цикле рассматриваются все возможные комбинации двух подстрок, из которых можно составить конкатенацией текущую. В итоге получаем ответ на задачу для данной подстроки.
Код на ideone.com. (C++)
Код на ideone.com. (Java)
Засчитанное решение на e-olymp.
Принято