3534923_ac_313ms_200k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <vector>
#include <string.h>
#include <algorithm>
#define inf 10000000

using namespace std;

typedef vector <int> VI;
VI sum, has;
char patterns[20][6][6];
int mark[20];
char tmp[6][6];

int minneed, X, Y;

int max(int a, int b)
{
	return a < b ? b : a;
}

int getNeed(VI a, VI b)
{
	int ret = 0;

	for (int i = 0; i < 5; i++)
	{
		ret += max(0, a[i]- b[i]);
	}
	return ret;
}

void combine()
{
	int i, j, k, t;

	for (i = 0; i < 5; i++)
	{
		for (j = 0; j < 5; j++)
		{
			tmp[i][j] = 'O';
		}
	}
	for (i = 0; i < X; i++)
	{
		if (mark[i] == 1)
		{
			for (j = 0; j < 5; j++)
			{
				for (k = 0; k < 5; k++)
				{
					if (patterns[i][j][k] == 'X')
					{
						tmp[j][k] = 'X';
					}
				}
			}
		}
	}
	tmp[2][2] = 'O';
	sum.clear();
	for (i = 0; i < 5; i++)
	{
		t = 0;
		for(j = 0; j < 5; j++)
		{
			t += (tmp[j][i] == 'X');
		}
		sum.push_back(t);
	}
	int need = getNeed(sum, has);
	if (need < minneed)
	{
		minneed = need;
	}
}

void dfs(int p, int n)
{
	if (n == 0)
	{
		combine();
		return ;
	}
	for (int i = p; i <= X - n; i++)
	{
		mark[i] = 1;
		dfs(i + 1, n - 1);
		mark[i] = 0;
	}
}

void enumeration(int n)
{
	dfs(0, n);
}

int main()
{
	int cas;
	int i, j, t;

	scanf("%d", &cas);
	while (cas-- > 0)
	{
		has.clear();
		minneed = inf;
		for (i = 0; i < 5; i++)
		{
			scanf("%d", &t);
			has.push_back(t);
		}
		scanf("%d%d", &X, &Y);
		for (i = 0; i < 5; i++)
		{
			for (j = 0; j < X; j++)
			{
				scanf("%s", patterns[j][i]);
			}
		}
		//for ( ; Y <= X; Y++)
		{
			memset(mark, 0, sizeof(mark));
			enumeration(Y);
		}
		printf("%d\n", minneed);
	}
	return 0;
}