Codeforces Round #243 (Div. 2)??Sereja and Table_html/css

Codeforces Round #243 (Div. 2)??Sereja and Table_html/css_WEB-ITnose

WBOY

Release： 2016-06-24 12:05:28

Original

894 people have browsed it

codeforces.com/contest/426/problem/D

Question:
First give the definition of connected block: for adjacent ( The same numbers (up, down, left and right) are regarded as a connected block
Now given an n*m rectangle with only 0 and 1 and the number k, find the minimum number of inversions so that the whole includes several rectangular connected blocks (i.e. Each connected block is a rectangle) (1?≤?n,?m?≤?100; 1?≤?k?≤?10)
If the minimum degree is greater than k, output -1

Analysis:
The characteristic of the question is that k is relatively small, which means that the number of reversals is relatively small, so you can start from here. It is definitely not possible to directly enumerate all positions, so you can think about it like this: (Let's assume n>=m) If n is larger than k, then there must be some rows that will not have reversed numbers, then we can enumerate Process each row; if k is larger than n, n is less than 10 at this time, so at this time we can violently enumerate all states of each row and then process.
The above two methods are based on the following graphic characteristics when processing. When you only know one line, you can find the minimum total number of reversals

In the end, it can only be
01010...
10101...
...
shape (one character represents a rectangle)

const int MAXN = 110;int ipt[MAXN][MAXN];int main(){//    freopen("in.txt", "r", stdin);	int n, m, k;	while (~RIII(n, m, k))	{		REP(i, n) REP(j, m) RI(ipt[i][j]);		if (n < m)		{			REP(i, n) FF(j, i + 1, m) swap(ipt[i][j], ipt[j][i]);			swap(n, m);		}		if (n > k)		{			int ans = INF;			REP(i, n)			{				int tans = 0;				REP(j, n)				{					int cnt = 0;					if (i == j) continue;					REP(k, m)					{						if (ipt[i][k] != ipt[j][k]) cnt++;					}					tans += min(cnt, m - cnt);				}				ans = min(ans, tans);			}			printf("%d\n", ans <= k ? ans: -1);		}		else		{			int ans = INF;			REP(i, n)			{				int all = 1 << m;				for (int q = 0; q < all; q++)				{					int diff = 0;					for (int t = 0, l = 1; t < m; l <<= 1, t++) if (((q & l) != 0) != ipt[i][t]) diff++;					if (diff > k) continue;					int tans = 0;					REP(j, n)					{						if (i == j) continue;						int cnt = 0;						for (int t = 0, l = 1; t < m; t++, l <<= 1) if (((q & l) != 0) != ipt[j][t]) cnt++;						tans += min(cnt, m - cnt);					}					ans = min(ans, diff + tans);				}			}			printf("%d\n", ans <= k ? ans: -1);		}	}	return 0;}

Copy after login