453B


  Posted on 06 Dec 2014
bitmask dynamic programming

Solution


#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;

#define D(x) 

const int MAX_N = 120;
const int MAX_A = 65;
const int INF = 0x3f3f3f3f;

int seq_a[MAX_N];
int seq_b[MAX_N];
int f[MAX_N][1 << 18];
int path[MAX_N][1 << 18];
int prime[20];
int factor_bits[MAX_A];
int num;
int n;

bool is_prime(int a)
{
	for (int i = 2; i <= a / 2; i++)
	{
		if (a % i == 0)
		{
			return false;
		}
	}
	return true;
}

int make_factor(int a)
{
	int ret = 0;
	for (int i = 0; i < num; i++)
	{
		ret <<= 1;
		if (a % prime[i] == 0)
		{
			ret = ret | 1;
		}
	}
	return ret;
}

void init()
{
	num = 0;
	for (int i = 2; i <= 60; i++)
	{
		if (is_prime(i))
		{
			prime[num++] = i;
		}
	}
	for (int i = 1; i < 60; i++)
	{
		factor_bits[i] = make_factor(i);
	}
}

void input()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &seq_a[i]);
	}
}

void work()
{
	memset(f, -1, sizeof(f));
	f[0][0] = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < (1 << num); j++)
		{
			if (f[i][j] == -1)
				continue;
			for (int k = 1; k < 60; k++)
			{
				if ((j & factor_bits[k]) != 0)
					continue;
				if (f[i + 1][j | factor_bits[k]] == -1 || f[i + 1][j | factor_bits[k]] > f[i][j] + abs(seq_a[i + 1] - k))
				{
					f[i + 1][j | factor_bits[k]] = f[i][j] + abs(seq_a[i + 1] - k);
					path[i + 1][j | factor_bits[k]] = k;
				}
			}
		}
	}
	int ans = INF;
	int temp;
	for (int i = 0; i < (1 << num); i++)
	{
		if (f[n][i] == -1)
			continue;
		if (ans > f[n][i])
		{
			ans = f[n][i];
			temp = i;
		}
	}
	for (int i = n; i > 0; i--)
	{
		seq_b[i] = path[i][temp];
		temp -= factor_bits[path[i][temp]];
	}

	for (int i = 1; i <= n; i++)
	{
		if (i != 1)
			putchar(' ');
		printf("%d", seq_b[i]);
	}
}

int main()
{
	init();
	input();
	work();
	return 0;
}