Domino
레이팅 미적용의견: 0
\(3^{rd}\) round, November \(28^{th}\) 2015
Mirko received an \(N \times N\) table for his birthday, where a n\(on-ne\)gative integer is written in each field
of the table. Unfortunately, the written numbers are too large for Mirko’s taste, so he will place K
dominoes on top of the table that will cover the fields that are too large.
More precisely, Mirko places the dominoes according to the following rules:
• each domino covers two fields of the table that are adjacent in a row or in a column,
• the dominoes do not overlap (but can touch),
• the sum of all visible (uncovered) fields needs to be as small as possible.
It is your task to determine the required minimal sum of visible fields. The test data will be such that
it will always be possible to place \(K\) dominoes without overlapping..
In test cases worth 70 points, it will hold \(K\) ⩽5.
The first line of input contains the integers \(N\) (1 ⩽\(N\) ⩽2000), the dimensions of the table, and \(K\)
(1 ⩽\(K\) ⩽8), the number of dominoes. Each of the following \(N\) lines contains \(N\) integers from the
interval [0, 1000]. These \(N \times N\) numbers describe Mirko’s table.
The first and only line of output must contain the minimal sum of visible fields after covering the table
with dominoes.
3 1
2 7 6
9 5 1
4 3 8
31
4 2
1 2 4 0
4 0 5 4
0 3 5 1
1 0 4 1
17
평가 및 의견
Domino
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Domino