Penafian: Kaedah yang diterangkan di bawah tidak universal, tetapi ia selalunya boleh menyelesaikan masalah atau membantu anda mendapatkan penyelesaian yang betul.
Jika terdapat satu set jurang yang terletak pada beberapa paksi (biasanya paksi masa atau indeks beberapa tatasusunan) dan anda perlu memilih beberapa daripadanya dengan cara yang optimum supaya jurang yang dipilih tidak bersilang, maka anda harus cuba menggunakan pengaturcaraan dinamik .
Skim penyelesaian anggaran:
Pada mulanya, kami mengisih jurang yang tersedia mengikut sempadan kanan. Mari kita mulakan dinamik berikut: dp[i] - jawapan untuk selang i pertama.
Kami akan mengira semula seperti berikut: pertama, pertimbangkan situasi bahawa selang ini tidak akan digunakan, kemudian hanya dp[i] = dp[i-1]. Ambil perhatian bahawa ini memastikan bahawa nilai dp[i] tidak berkurangan semasa i berkembang. Dan ini adalah logik, kerana. menambah jurang baharu, kita tidak boleh memburukkan lagi jawapan global: sama ada kita hanya mengabaikan jurang baharu itu, atau kita membina varian yang lebih menguntungkan menggunakannya. Sekarang, jika kita ingin menggunakan jurang ke-i, maka kita boleh menggunakan jurang yang sempadan kanannya kurang daripada sempadan kiri jurang semasa, kerana kita mesti memilih satu set jurang tidak bertindih. Untuk melakukan ini, kami mula-mula mengisih jurang mengikut sempadan kanan, supaya kini kami boleh mencari kedudukan yang diperlukan dengan cekap. Ini boleh dilakukan secara analitikal, jika boleh, tetapi dalam kes umum adalah mungkin untuk mencari jurang dengan binsearch, sempadan kanan yang kurang daripada sempadan kiri semasa dan, pada masa yang sama, maksimum yang mungkin. satu. Kami mahu memaksimumkan sempadan yang betul atas alasan tamak, kerana apabila saya membesar, jawapannya hanya boleh meningkat. Sehubungan itu, kami mencari kedudukan p yang diperlukan dan mengira semula dp[i] melalui dp[p] dan selang ke-i.