CF453B Little Pony and Harmony Chest <状压DP>

Problem

Little Pony and Harmony Chest

$\mathrm{Time\;limit:\;4000\;ms}$
$\mathrm{Memory\;limit:\;262144\;KB}$

Description

Princess Twilight went to Celestia and Luna’s old castle to research the chest from the Elements of Harmony.


A sequence of positive integers $b_i$ is harmony if and only if for every two elements of the sequence their greatest common divisor equals $1$. According to an ancient book, the key of the chest is a harmony sequence bi which minimizes the following expression:

$$\sum_{i=1}^{n}{|a_i-b_i|}$$

You are given sequence $a_i$, help Princess Twilight to find the key.

Input

The first line contains an integer $n (1\le n\le 100)$ — the number of elements of the sequences $a$ and $b$. The next line contains $n$ integers $a_1,a_2,\cdots,a_n (1\le a_i\le 30)$.

Output

Output the key — sequence bi that minimizes the sum described above. If there are multiple optimal sequences, you can output any of them.

Example

Input #1

5
1 1 1 1 1

Output #1

1 1 1 1 1 

Input #2

5
1 6 4 2 8

Output #2

1 5 3 1 8 

标签：状压DP

Translation

题目大意：给出一个$n$个元素的序列$a$，要求找一个$n$个元素的序列$b$，使得$b$中的数两两互质，且要最小化$|a_i-b_i|$之和。

Solution

对于互质的条件，发现其相当于每个质因子只能用一次（$1$可以用无限次）。发现$a_i$的范围只有$30$，而如果$b_i\ge 2\times a_i$，则取$1$会更优。因此质因子只可能在$1\sim 60$之间，只有$17$个，可以状压。
预处理$1\sim 60$中所有数占用的质因子状态，存在数组$sta[]$中。
$f[i][j]$表示当前选到第$i$个数，质因子的选择状态为$j$的最大答案。
对于一个数$k$，若 $j\&sta[k]\ne 0$，则不能选。
否则有 $f[i+1][j|sta[k]] = max(f[i+1][j|sta[k]], f[i][j]+abs(a[i+1]-k))$
对于输出方案，存下转移到$f[i][j]$的状态$g[i][j]$和选的数$h[i][j]$，递归输出即可。

Code

#include <bits/stdc++.h>
#define SZ 17
#define MX 60
#define MAX_N 100
#define INF 0x3f3f3f3f
using namespace std;
int pri[SZ] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59};
int n, a[MAX_N+5], f[MAX_N+5][1<<SZ], g[MAX_N+5][1<<SZ], h[MAX_N+5][1<<SZ], sta[MX];
void init() {
    for (int i = 0; i <= n; i++) for (int j = 0; j < (1<<SZ); j++)
        f[i][j] = INF, g[i][j] = h[i][j] = 0;
    f[0][0] = 0;	memset(sta, 0, sizeof sta);
}
void prt(int i, int j) {if (!i) return;    prt(i-1, g[i][j]), printf("%d ", h[i][j]);}
int main() {
    while (~scanf("%d", &n)) {
        init(); for (int i = 1; i <= n; i++) scanf("%d", a+i);
        for (int i = 2; i < MX; i++) for (int j = 0; j < SZ; j++)
            if (i%pri[j] == 0) sta[i] |= (1<<j);
        for (int i = 0; i < n; i++) for (int j = 0; j < (1<<SZ); j++) {
            if (f[i][j] == INF) continue;
            for (int k = 1; k < MX; k++) {
                if (j&sta[k]) continue;
                if (f[i+1][j|sta[k]] > f[i][j]+abs(a[i+1]-k))
                    f[i+1][j|sta[k]] = f[i][j]+abs(a[i+1]-k), 
                    g[i+1][j|sta[k]] = j, h[i+1][j|sta[k]] = k;
            }
        }
        int pos = -1, ans = INF;
        for (int i = 0; i < (1<<SZ); i++) if (f[n][i] < ans)
            pos = i, ans = f[n][i];
        prt(n, pos), puts("");
    }
    return 0;
}