1

Честно, понятия не имею, в чём может заключаться ошибка. Но она есть. Ошибка точно не в дп, а в его раскрутке.

int n, m;
vector<int> a, b;

cin >> n;
a.resize(n);
for(auto &x : a) cin >> x;

cin >> m;
b.resize(m);
for(auto &x : b) cin >> x;

vector<vector<int>> dp(a.size() + 1, vector<int>(b.size() + 1, 0));
for(int i = 0; i < a.size(); i++) {
    for(int j = 0; j < b.size(); j++) {
        ///Because dp have 0-barrier and a,b do not. (protection of going abroad)
        int ii = i + 1, jj = j + 1;
        if(a[i] == b[j]) dp[ii][jj] = dp[ii - 1][jj - 1] + 1;
        else dp[ii][jj] = max(dp[ii - 1][jj], dp[ii][jj - 1]);
    }
}

vector<int> ans;
for(int i = a.size(), j = b.size(); i != 0 && j != 0; ) {
    if(dp[i][j] == dp[i - 1][j - 1] + 1) {
        ans.push_back(a[i - 1]);
        i--, j--;
    } else {
        if(dp[i - 1][j] > dp[i][j - 1]) i--;
        else j--;
    }
}

//cout << dp[a.size()][b.size()] << endl;
reverse(ans.begin(), ans.end());
for(auto &x : ans) cout << x << " ";

Протестировать можно тут: https://informatics.msk.ru/mod/statements/view3.php?id=6433&chapterid=1790#1

Логин и пароль от временного аккаунта: testacc2

4
  • Если внимательное чтение кода не помогает, то есть смысл напридумывать различных примеров с разными ситуациями. Если придумывание тестов тоже не помогло, то ещё можно написать медленное решение в лоб (перебирающее все подпоследовательности) и генератор тестов небольшой длины (рандомных последовательностей, скажем, длиной до 100), сгенерировать много тестов, и прогнать на каждом тесте медленное но точно верно работающее решение и сравнить его результат с вашим ДП решением. У вас же компьютер в руках, пусть он Вам и поможет найти ошибку.
    – vt-egorov
    Commented 13 июл. 2018 в 18:46
  • в векторе dp у вас a,size() + 1 штук веткторов, содержащие только нули, и вы дальше присваиваете один обьект со значением нуль другому обьекту тоже с нулевым значением. И вообше зачем нужны эти длинные мучительные коды, когда можно все это делать 10 раз проще? Есть и другие ошибки... Commented 13 июл. 2018 в 19:55
  • @ARHovsepyan Я не просто присваиваю, а ещё добавляю единицу. Как я написал в вопросе, с самим ДП проблем нет, проблемы именно с его раскруткой. Да, можно в 10 раз проще, но тогда будет в более чем 10 раз медленнее. Другое решение это полный перебор сложностью ~O(n^5), а тут у меня динамика сложностью O(n^2) при худшем случае. Commented 13 июл. 2018 в 20:26
  • @Егор Левоненко, с временем нынче туго. Постараюсь вечером с вами это все обсуждать (ваш код и другое решение). Мне самому интересно... Commented 14 июл. 2018 в 8:56

1 ответ 1

2

Ошибка вкралась в выборе обратного хода по диагонали - тут нужно ориентироваться не на значение в таблице, а на равенство символов в исходных строках

// if(dp[i][j] == dp[i - 1][j - 1] + 1) заменить на
 if(a[i-1] == b[j-1])

а уж если они не равны, то ход влево-вверх выбирается по максимуму (тут, похоже, всё верно)

Смысл в том, чтобы восстановить обратный путь с помощью тех же условий, что использовались при прямом ходе (чтобы не использовать дополнительную таблицу для хранения направлений переходов)

Вот пример из русской вики

          A   B   C   B
      0   0   0   0   0
D     0 ← 0 ← 0 ← 0 ← 0
C     0 ← 0 ← 0 ↖ 1 ← 1
B     0 ← 0 ↖ 1 ← 1 ↖ 2
A     0 ↖ 1 ← 1 ← 1 ↑ 2

Выбор обратного хода по таблице dp из последней ячейки ведёт по диагонали и соответствие B-B не будет засчитано, в то время как правильный прямой ход в эту ячейку шёл по вертикали

4
  • сейчас проверить не могу... Но разве это должно работать? i, j начинаются с a.size() и b.size() соответственно. А значит, если мы будем так сравнивать, мы вывалимся за границы массива.. Полагаю, вы имели в виду 'if(a[i - 1] == b[j - 1])'? Commented 14 июл. 2018 в 7:29
  • Точно, я просто скопировал условие из прямого хода.
    – MBo
    Commented 14 июл. 2018 в 10:02
  • Да, это работает.. Но не могу понять, почему. Ведь если a[i-1] == b[j - 1], значит и dp[i][j] == dp[i - 1][j - 1] + 1, потому что второе следует из первого. Разве это не так? Объясните, пожалуйста. Commented 14 июл. 2018 в 12:09
  • Второе следует из первого, но первое не обязательно следует из второго. Такое соотношение значений dp может получиться и при вертикальном и горизонтальном шаге. Добавил пример
    – MBo
    Commented 14 июл. 2018 в 12:24

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.