Problem
Anda perlu melakukan n kerja yang berbeza. Dalam kes ini, anda mempunyai senarai n tukang dan harga, untuk berapa ringgit pekerja yang melakukan kerja.
Agihkan pekerja supaya anda membelanjakan lebih sedikit wang secara keseluruhan. Pada masa yang sama, anda mahu melakukan segala-galanya dalam satu hari, jadi pekerja akan bekerja secara selari. Oleh itu, setiap pekerja akan melaksanakan satu tugasan.
Input:
Dalam baris pertama anda diberi nombor positif n (1 <= n <= 8) - bilangan pekerjaan dan pekerja.
N baris seterusnya mengandungi n integer positif yang dipisahkan oleh ruang - matriks A, dengan A
i,j menunjukkan berapa dolar nombor pekerja i akan melakukan kerja nombor j. Untuk semua A
i,j 1 <= A
i,j <= 10
5.
Output:
Cetak satu nombor - kos minimum yang anda boleh ambil pekerja ini untuk semua pekerjaan yang tersedia.
Contoh:
| Input |
Output |
3
3 1 2
5 6 4
7 8 9
| 12 |
Penjelasan:
Pekerja pertama akan melakukan pekerjaan kedua, pekerja kedua pekerjaan ketiga, dan pekerja ketiga pekerjaan pertama. Jumlah kos ialah 1 + 4 + 7 = 12.