CF453B Little Pony and Harmony Chest <状压DP>

Problem

Little Pony and Harmony Chest

Time limit:
Memory limit:

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 is harmony if and only if for every two elements of the sequence their greatest common divisor equals . According to an ancient book, the key of the chest is a harmony sequence bi which minimizes the following expression:

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

Input

The first line contains an integer — the number of elements of the sequences and . The next line contains integers .

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

1
2
5
1 1 1 1 1

Output #1

1
1 1 1 1 1

Input #2

1
2
5
1 6 4 2 8

Output #2

1
1 5 3 1 8

标签:状压DP

Translation

题目大意:给出一个 个元素的序列 ,要求找一个 个元素的序列 ,使得 中的数两两互质,且要最小化 之和。

Solution

对于互质的条件,发现其相当于每个质因子只能用一次( 可以用无限次)。发现 的范围只有 ,而如果 ,则取 会更优。因此质因子只可能在 之间,只有 个,可以状压。
预处理 中所有数占用的质因子状态,存在数组 中。
表示当前选到第 个数,质因子的选择状态为 的最大答案。
对于一个数 ,若 ,则不能选。
否则有
对于输出方案,存下转移到 的状态 和选的数 ,递归输出即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#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;
}
------------- Thanks For Reading -------------
0%