Kos Minimum untuk Menghubungkan Dua Kumpulan Mata
1595. Kos Minimum untuk Menghubungkan Dua Kumpulan Mata
Kesukaran: Sukar
Topik: Tatasusunan, Pengaturcaraan Dinamik, Manipulasi Bit, Matriks, Bitmask
Anda diberi dua kumpulan mata di mana kumpulan pertama mempunyai saiz1 mata, kumpulan kedua mempunyai saiz2 mata, dan saiz1 > = saiz2.
Kos sambungan antara mana-mana dua titik diberikan dalam saiz1 x saiz2 matriks dengan kos[i][j] ialah kos penyambungan titik i daripada kumpulan pertama dan titik j kumpulan kedua. Kumpulan disambungkan jika setiap titik dalam kedua-dua kumpulan disambungkan kepada satu atau lebih titik dalam kumpulan bertentangan. Dalam erti kata lain, setiap titik dalam kumpulan pertama mesti disambungkan kepada sekurang-kurangnya satu titik dalam kumpulan kedua dan setiap titik dalam kumpulan kedua mesti disambungkan kepada sekurang-kurangnya satu titik dalam kumpulan pertama.
Pulangan kos minimum yang diperlukan untuk menyambung dua kumpulan.
Contoh 1:
- Input: kos = [[15, 96], [36, 2]]
- Output: 17
- Penjelasan: Cara optimum untuk menghubungkan kumpulan ialah:
1--A 2--B This results in a total cost of 17.
Contoh 2:
- Input: kos = [[1, 3, 5], [4, 1, 1], [1, 5, 3]]
- Output: 4
- Penjelasan: Cara optimum untuk menghubungkan kumpulan ialah:
1--A 2--B 2--C 3--A This results in a total cost of 4.
Perhatikan bahawa terdapat berbilang titik disambungkan ke titik 2 dalam kumpulan pertama dan titik A dalam kumpulan kedua. Ini tidak penting kerana tiada had bilangan mata yang boleh disambungkan. Kami hanya mengambil berat tentang jumlah kos minimum.
Contoh 3:
- Input: kos = [[2, 5, 1], [3, 4, 7], [8, 1, 2], [6, 2, 4], [3, 8, 8] ]
- Output: 10
Kekangan:
- saiz1 == kos.panjang
- saiz2 == kos[i].panjang
- 1 <= saiz1, saiz2 <= 12
- saiz1 >= saiz2
- 0 <= kos[i][j] <= 100
Petunjuk:
- Setiap titik di sebelah kiri sama ada akan disambungkan ke titik tepat yang telah disambungkan ke beberapa nod kiri, atau subset nod di sebelah kanan yang tidak disambungkan ke mana-mana nod
- Gunakan pengaturcaraan dinamik dengan bitmasking, di mana keadaan akan berada (bilangan mata yang diberikan dalam kumpulan pertama, bitmask mata yang diberikan dalam kumpulan kedua).
Penyelesaian:
Kami boleh memanfaatkan pengaturcaraan dinamik dengan bitmasking. Ideanya adalah untuk meminimumkan kos dengan mempertimbangkan setiap titik dalam kumpulan pertama dan cuba menyambungkannya ke semua titik dalam kumpulan kedua.
Pendekatan Pengaturcaraan Dinamik (DP) dengan Bitmasking
Langkah-langkah:
-
Perwakilan Negeri:
- Gunakan dp jadual DP[i][topeng] di mana:
- i ialah indeks dalam kumpulan pertama (dari 0 hingga saiz1-1).
- mask ialah bitmask yang mewakili titik mana dalam kumpulan kedua telah disambungkan.
- Gunakan dp jadual DP[i][topeng] di mana:
-
Peralihan Negeri:
- Untuk setiap titik dalam kumpulan pertama, cuba sambungkannya ke setiap titik dalam kumpulan kedua, kemas kini jadual DP dengan sewajarnya.
- Jika titik baharu dalam kumpulan kedua disambungkan, kemas kini bit yang sepadan dalam topeng.
-
Kes Asas:
- Mulakan dengan dp[0][0] = 0 (tiada sambungan pada mulanya).
-
Matlamat:
- Kira kos minimum untuk dp[saiz1][(1 << saiz2) - 1], yang mewakili penyambungan semua titik daripada kedua-dua kumpulan.
Mari laksanakan penyelesaian ini dalam PHP: 1595. Kos Minimum untuk Menghubungkan Dua Kumpulan Mata
Penjelasan:
- Dp tatasusunan DP[i][mask] menyimpan kos minimum untuk menyambung mata i pertama daripada kumpulan 1 dengan mata dalam kumpulan 2 seperti yang ditunjukkan oleh topeng.
- Gelung bersarang berulang pada setiap gabungan i dan mask, cuba mencari kos optimum dengan mempertimbangkan semua sambungan yang mungkin.
- Akhirnya, penyelesaian mengira kos minimum mengambil kira senario di mana beberapa titik dalam kumpulan kedua mungkin masih tidak disambungkan, memastikan semua titik disambungkan.
Pendekatan ini mengendalikan kekangan masalah dengan cekap dan memastikan kos minimum untuk menyambungkan dua kumpulan.
Pautan Kenalan
Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberi repositori bintang di GitHub atau berkongsi siaran pada rangkaian sosial kegemaran anda ?. Sokongan anda amat bermakna bagi saya!
Jika anda mahukan kandungan yang lebih berguna seperti ini, sila ikuti saya:
- GitHub
Atas ialah kandungan terperinci Kos Minimum untuk Menghubungkan Dua Kumpulan Mata. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

Alat AI Hot

Undress AI Tool
Gambar buka pakaian secara percuma

Undresser.AI Undress
Apl berkuasa AI untuk mencipta foto bogel yang realistik

AI Clothes Remover
Alat AI dalam talian untuk mengeluarkan pakaian daripada foto.

Clothoff.io
Penyingkiran pakaian AI

Video Face Swap
Tukar muka dalam mana-mana video dengan mudah menggunakan alat tukar muka AI percuma kami!

Artikel Panas

Alat panas

Notepad++7.3.1
Editor kod yang mudah digunakan dan percuma

SublimeText3 versi Cina
Versi Cina, sangat mudah digunakan

Hantar Studio 13.0.1
Persekitaran pembangunan bersepadu PHP yang berkuasa

Dreamweaver CS6
Alat pembangunan web visual

SublimeText3 versi Mac
Perisian penyuntingan kod peringkat Tuhan (SublimeText3)

Input suara pengguna ditangkap dan dihantar ke backend PHP melalui API Mediarecorder JavaScript front-end; 2. PHP menjimatkan audio sebagai fail sementara dan memanggil STTAPI (seperti Pengiktirafan Suara Google atau Baidu) untuk mengubahnya menjadi teks; 3. PHP menghantar teks kepada perkhidmatan AI (seperti Openaigpt) untuk mendapatkan jawapan pintar; 4. PHP kemudian memanggil TTSAPI (seperti sintesis Baidu atau Google Voice) untuk menukar balasan ke fail suara; 5. PHP mengalir fail suara kembali ke bahagian depan untuk bermain, menyelesaikan interaksi. Seluruh proses dikuasai oleh PHP untuk memastikan hubungan lancar antara semua pautan.

Kaedah teras untuk membina fungsi perkongsian sosial dalam PHP adalah untuk menghasilkan pautan perkongsian secara dinamik yang memenuhi keperluan setiap platform. 1. Mula -mula dapatkan halaman semasa atau URL dan maklumat artikel yang ditentukan; 2. Gunakan urlencode untuk menyandikan parameter; 3. Sambutan dan menjana pautan perkongsian mengikut protokol setiap platform; 4. Pautan paparan di hujung depan untuk pengguna mengklik dan berkongsi; 5. Dinamik menghasilkan tag OG pada halaman untuk mengoptimumkan paparan kandungan perkongsian; 6. Pastikan untuk melepaskan input pengguna untuk mencegah serangan XSS. Kaedah ini tidak memerlukan pengesahan yang kompleks, mempunyai kos penyelenggaraan yang rendah, dan sesuai untuk kebanyakan keperluan perkongsian kandungan.

Untuk merealisasikan pembetulan ralat teks dan pengoptimuman sintaks dengan AI, anda perlu mengikuti langkah -langkah berikut: 1. Pilih model AI atau API yang sesuai, seperti Baidu, Tencent API atau perpustakaan NLP sumber terbuka; 2. Panggil API melalui curl atau Guzzle PHP dan memproses hasil pulangan; 3. Maklumat pembetulan ralat paparan dalam aplikasi dan membenarkan pengguna memilih sama ada untuk mengadopsinya; 4. Gunakan php-l dan php_codesniffer untuk pengesanan sintaks dan pengoptimuman kod; 5. Secara berterusan mengumpul maklum balas dan mengemas kini model atau peraturan untuk meningkatkan kesannya. Apabila memilih AIAPI, fokus pada menilai ketepatan, kelajuan tindak balas, harga dan sokongan untuk PHP. Pengoptimuman kod harus mengikuti spesifikasi PSR, gunakan cache yang munasabah, elakkan pertanyaan bulat, mengkaji semula kod secara berkala, dan gunakan x

1. Memaksimumkan nilai komersil sistem komen memerlukan menggabungkan pengiklanan pengiklanan asli, perkhidmatan nilai tambah pengguna (seperti memuat naik gambar, komen top-up), mempengaruhi mekanisme insentif berdasarkan kualiti komen, dan pematuhan data pengewangan data tanpa nama; 2. Strategi audit harus mengadopsi gabungan penapisan kata kunci dinamik pra-audit dan mekanisme pelaporan pengguna, ditambah dengan penarafan kualiti komen untuk mencapai pendedahan hierarki kandungan; 3. Anti-brushing memerlukan pembinaan pertahanan berbilang lapisan: Recaptchav3 Pengesahan tanpa sensor, Honeypot Honeypot Field Robot, IP dan Had Frekuensi Timestamp menghalang penyiraman, dan pengiktirafan corak kandungan menandakan komen yang mencurigakan, dan terus berurusan dengan serangan.

PHP tidak secara langsung melaksanakan pemprosesan imej AI, tetapi mengintegrasikan melalui API, kerana ia adalah baik pada pembangunan web dan bukannya tugas-tugas intensif pengkomputeran. Integrasi API boleh mencapai pembahagian profesional buruh, mengurangkan kos, dan meningkatkan kecekapan; 2. Mengintegrasikan teknologi utama termasuk menggunakan Guzzle atau Curl untuk menghantar permintaan HTTP, pengekodan data JSON dan penyahkodan, pengesahan keselamatan utama API, pemprosesan giliran yang memakan masa yang memakan masa, pengendalian ralat yang teguh dan mekanisme semula, penyimpanan imej dan paparan; 3. Cabaran umum termasuk kos API daripada kawalan, hasil generasi yang tidak terkawal, pengalaman pengguna yang lemah, risiko keselamatan dan pengurusan data yang sukar. Strategi tindak balas menetapkan kuota dan cache pengguna, menyediakan panduan propt dan pemilihan multi-gambar, pemberitahuan asynchronous dan kemajuan kemajuan, penyimpanan pembolehubah persekitaran utama dan audit kandungan, dan penyimpanan awan.

PHP memastikan pemotongan inventori atomik melalui urus niaga pangkalan data dan kunci baris forupdate untuk mengelakkan overselling serentak yang tinggi; 2. Konsistensi inventori pelbagai platform bergantung kepada pengurusan berpusat dan penyegerakan yang didorong oleh peristiwa, menggabungkan pemberitahuan API/webhook dan beratur mesej untuk memastikan penghantaran data yang boleh dipercayai; 3. Mekanisme penggera harus menetapkan inventori rendah, sifar/inventori negatif, jualan yang tidak dapat dilepaskan, kitaran penambahan dan strategi turun naik yang tidak normal dalam senario yang berbeza, dan pilih DingTalk, SMS atau orang yang bertanggungjawab e -mel mengikut urgensi, dan maklumat penggera mesti lengkap dan jelas untuk mencapai penyesuaian perniagaan dan tindak balas yang cepat.

1. 2. Prestasi tinggi memerlukan pergantungan pada cache (redis), pengoptimuman pangkalan data, CDN dan giliran tak segerak; 3. Keselamatan mesti dilakukan dengan penapisan input, perlindungan CSRF, HTTPS, penyulitan kata laluan dan kawalan kebenaran; 4. Pengiklanan pilihan wang, langganan ahli, ganjaran, komisen, pembayaran pengetahuan dan model lain, terasnya adalah untuk memadankan nada komuniti dan keperluan pengguna.

Phpisstillrelevantinmodernenterpriseenvironments.1.modernphp (7.xand8.x) Menawarkan Perpaduan Perlengkapan, ketegangan, jitcompilation, danmodernsyntax, makeitsuatableforlarge-scaleapplications.2.phpintegratefective
