а строительства мостов сформулирована следующим образом:

Есть река, которая течет горизонтально через область. Есть множество городов выше и ниже реки. Каждый город над рекой сопоставляется с городом под рекой, и вы получаете это соответствие в виде набора пар.

Вы заинтересованы в создании набора мостов через реку, чтобы соединить наибольшее количество совпадающих пар городов, но вы должны сделать это так, чтобы никакие два моста не пересекались друг с другом.

Разработайте алгоритм, чтобы решить эту проблему максимально эффективно.

Я слышал, что эта проблема связана ссамая длинная возрастающая подпоследовательность проблема, но я не вижу, как использовать это здесь. Например, если нам дают пары

2  5  8  10
6  4  1  2

Тогда какую последовательность мы рассмотрим для LIS?

Спасибо!