Courses

Pengaturcaraan dinamik

Corak dalam Pengaturcaraan Dinamik - 2

Module: Corak dalam Pengaturcaraan Dinamik - 2

Problem

4 /5

kerdil

Theory Click to read/hide

Penafian: Kaedah yang diterangkan di bawah tidak universal, tetapi ia selalunya boleh menyelesaikan masalah atau membantu anda mendapatkan penyelesaian yang betul.

Jika anda perlu menyemak kewujudan pilih atur dalam masalah, atau mencari bilangan pilih atur yang sepadan, atau sesuatu yang serupa, maka anda harus mempertimbangkan untuk menggunakan pengaturcaraan subset dinamik.

Parameter utama ialah bitmask, yang akan menunjukkan elemen yang telah dimasukkan dalam pilih atur, dan yang tidak. Juga sering diperlukan ialah parameter kedua yang menunjukkan elemen yang terakhir disertakan.

Selalunya pilih atur boleh dilihat dalam konteks laluan dalam graf. Sehubungan itu, mari kita pertimbangkan contoh klasik - masalah laluan Hamiltonian.
Laluan Hamiltonian ialah laluan mudah yang melalui setiap bucu graf tepat sekali. Ia boleh diwakili hanya sebagai pilih atur panjang n, dengan n ialah bilangan bucu. Susunan dalam pilih atur ini akan menunjukkan susunan bucu dalam laluan ini dilalui.

Untuk menyemak kehadiran laluan Hamiltonian dalam graf, mari kita mulakan dinamik dp[mask][last] - adakah terdapat laluan mudah yang memintas bucu yang ditandakan dengan yang dalam bitmask topeng dan berakhir di bucu terakhir.
Nilai awal ialah dp[2ⁱ][i] = benar, selebihnya palsu, yang bermaksud bahawa sentiasa ada laluan kosong bermula pada mana-mana bucu.
Mempunyai nilai true dalam dp[mask][last] kita akan membuat peralihan ke hadapan, dalam erti kata "memperluaskan laluan". Iaitu, kita akan mencari nombor bucu yang ditandakan dengan sifar dalam topeng (kami belum melawatnya dalam perjalanan) dan pada masa yang sama supaya terdapat kelebihan dari akhir ke puncak ini (laluan mesti dilanjutkan dengan tepi sedia ada). Iaitu, kami melakukan dp[mask | 2^k][k] = benar jika dp[mask][last] = benar DAN topeng & 2^k = 0 (bucu k belum lagi dilawati) Dan ada tepi terakhir -> k.
Akhirnya, laluan Hamiltonian wujud jika terdapat nilai sebenar dalam dp untuk parameter bitmask semua-satu dan sebarang bucu terakhir.

Problem

Pernah Quark kerdil terjumpa peta harta karun. Terdapat N titik yang ditandakan pada peta di mana harta itu boleh ditemui. Semua titik dinomborkan dari 1 hingga N. Bagi setiap pasangan mata, Quark mengetahui panjang jalan yang menghubungkannya. Quark memulakan pencariannya dari titik nombor 1. Sebelum memulakan perjalanannya yang jauh, kerdil yang licik itu melintasi titik di mana, pada pendapatnya, tidak ada harta karun. Ia dijamin bahawa mata nombor 1 tidak pernah dicoret. Selepas itu, Quark memilih beberapa laluan yang melalui semua titik yang tinggal pada peta. Laluan tidak melalui titik yang sama lebih daripada sekali. Quark hanya boleh berjalan di jalan raya yang menghubungkan titik-titik yang tidak bersilang.

Quark mahu memilih laluan dengan panjang minimum. Ia adalah perlu untuk mencari laluan sedemikian untuk Quark.

Input
Baris pertama mengandungi satu integer N (1 ≤ N ≤ 15) — bilangan titik yang ditanda pada peta. Garis N seterusnya mengandungi jarak antara titik. Baris (i+1)-th mengandungi N integer d_i1,d_i2, d_iN — panjang jalan dari titik ke-i ke semua yang lain. Dijamin bahawa d_ij=d_ji, d_ii=0 dan 0 <d_ij < 100 . Baris ke (N+2) mengandungi satu integer Q (1 < Q ≤ 1000) — bilangan pilihan untuk memadam mata untuk peta ini. Baris Q berikut mengandungi penerangan tentang pilihan untuk pemadaman. Penerangan bermula dengan nombor C (0 ≤ C < N) — bilangan mata di mana, menurut Quark, harta itu tidak boleh. Nombor C seterusnya memberikan nombor titik ini.

Cetakan
Cetak garisan Q. Dalam setiap baris cetak satu integer — panjang laluan minimum dengan pilihan yang sepadan untuk memadam mata.