Penafian: Kaedah yang diterangkan di bawah tidak universal, tetapi ia selalunya boleh menyelesaikan masalah atau membantu anda mendapatkan penyelesaian yang betul.
Jika masalahnya berpunca daripada fakta bahawa adalah perlu untuk membahagikan tatasusunan kepada subsegmen yang tidak bersilang (urutan elemen berturut-turut) dengan cara yang optimum (atau mengira bilangan pemisahan yang sesuai), maka ia patut dicuba untuk menyelesaikannya menggunakan pengaturcaraan dinamik.
Contoh skema penyelesaian adalah seperti berikut:
dp[i] - respons untuk elemen i pertama
Mengira dp[i]: memandangkan kita hanya mempertimbangkan elemen i pertama, elemen ke-i akan menjadi yang terakhir, yang bermaksud bahawa elemen ini akan berada dalam subsegmen terakhir dan, pada masa yang sama, elemen paling kanan di sana. Oleh itu, kita boleh lelaran melepasi sempadan kiri subsegmen terakhir j. Dalam proses penghitungan, kita akan mengira nilai subsegmen ini, dan jika betul, maka kita akan mengira semula dp[i] hingga dp[j - 1] dan nilai subsegmen [j;i].
Pertimbangkan masalah mudah berikut: memandangkan tatasusunan integer, anda perlu membahagikannya kepada bilangan minimum subsegmen tidak bersilang supaya setiap nombor dimasukkan dalam beberapa subsegmen dan setiap subsegmen mengandungi nombor yang sama. Contohnya, untuk tatasusunan 1 2 2 3 3 3 2 1 1, partition optimum kelihatan seperti ini: [1] [2 2] [3 3 3] [2] [1 1]. Tugas ini mudah diselesaikan dengan hanya melalui tatasusunan (kami meletakkan semua elemen berturut-turut yang sama dalam satu subsegmen), tetapi kami akan menyelesaikannya menggunakan pengaturcaraan dinamik sebagai contoh.
intn;
cin>> n;
// isikan tatasusunan dengan 1-index
vektor arr(n + 1);
untuk (int i = 1; i <= n; i++)
cin>> arr[i];
// pada mulanya tetapkan +oo kepada nilai dp
vektor dp(n + 1, 1000000000);
// susunan panjang sifar tidak perlu dipecah, jadi jawapan untuknya ialah 0
dp[0] = 0;
// hitung jawapan untuk dp[i] dalam menaik i
untuk (int i = 1; i <= n; i++) {
// pada masa ini arr[i] ialah elemen terakhir, jadi ia akan menjadi nombor paling kanan dalam subsegmen terakhir
// gelung melalui semua pilihan untuk tempat subsegmen terakhir ini bermula
untuk (int j = i; j > 0; j--) {
jika (arr[j] != arr[i]) {
// jika anda bertemu elemen yang tidak sama dengan yang terakhir, maka subsegmen akan mengandungi nombor yang berbeza, dan ini tidak sesuai dengan syarat
// tidak ada gunanya meneruskan, kerana mengalihkan sempadan kiri ke kiri, elemen ini tidak akan hilang, jadi kita pecah
pecah;
}
// bayangkan subsegmen terakhir ialah [j;i]
// jadi anda perlu mengambil partition optimum bagi elemen j-1 pertama dan tambah 1 (subsegmen [j; i] itu sendiri)
dp[i] = min(dp[i], dp[j - 1] + 1);
}
}
cout << dp[n];
Jika elemen mungkin tidak tergolong dalam mana-mana subsegmen, maka anda hanya perlu mempertimbangkan pilihan yang sesuai, kerana dp[i] = dp[i - 1]
|
Jika perlu untuk membahagikan tatasusunan kepada betul-betul k subsegmen, maka parameter kedua hanya ditambah dalam pengaturcaraan dinamik - berapa banyak segmen untuk dibahagikan.
Iaitu, sekarang kita akan mempertimbangkan dp berikut:
dp[i][j] ialah jawapan untuk elemen i pertama, jika kita membahagikannya kepada segmen j yang tepat.
Berhati-hati dengan keadaan tidak sah.
Pengiraan semula dinamik adalah sama, tetapi mengambil kira parameter kedua. Iaitu, mengira dp[i][k] dan mengisih melalui sempadan kiri subsegmen terakhir j, kita mengira semula dp[i][k] melalui dp[j - 1][k - 1] dan nilai segmen [j;i].
|
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.
|