[CodeForces 453B] Little Pony and Harmony Chest

https://codeforces.ml/contest/453/problem/B

题意：
给定序列\(a(1 \leq a_i \leq 30)\)，求等长序列\(b\)，满足\(b\)序列中任意两个数都是互质的，且\(\sum_1^n\lvert a_i - b_i\rvert\)尽量小。

思路：
互质要求两个数之间没有相同的质因子。一个首先的想法是1肯定能直接满足。看一下\(a_i\)的范围，发现如果\(b_i\)的值没有比\(2 * a_i\)小的时候，我们不如直接取\(1\)。由此确立了\(b_i\)的范围为\([1, 60)\)。小于\(60\)的素数只有\(16\)个，数据范围很小，考虑状压\(dp\)，把拥有的质因数的情况压缩一下，发现就比较好写了，再记录下路径即可。

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"

inline int rd() {
    int f = 0; int x = 0; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) f |= (ch == ‘-‘);
    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - ‘0‘;
    if (f) x = -x;
    return x;
}

typedef long long ll;

const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int N = 1e2 + 7;
const int M = (1 << 16);

int n, m = (1 << 16) - 1;
int prime[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53};
int a[N], b[N], sta[N];
int dp[N][M], path[N][M];

void init() {
    for (int i = 0; i < 16; ++i) {
        int f = prime[i];
        for (int j = f; j < 60; j += f) {
            sta[j] |= 1 << i;
        }
    }
    memset(dp, 0x3f, sizeof(dp));
}

void solve() {
    n = rd();
    init();
    for (int i = 1; i <= n; ++i) {
        a[i] = rd();
    }
    dp[0][0] = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= m; ++j) {
            for (int k = 1; k < 60; ++k) {
                if ((sta[k] & j) == 0) {
                    int to = j | sta[k];
                    if (dp[i][to] > dp[i - 1][j] + abs(a[i] - k)) {
                        dp[i][to] = dp[i - 1][j] + abs(a[i] - k);
                        path[i][to] = k;
                    }
                }
            }
        }
    }
    int s = 0;
    int minn = inf;
    for (int j = 0; j <= m; ++j) {
        if (dp[n][j] < minn) {
            minn = dp[n][j];
            s = j;
        }
    }
    for (int i = n; i >= 1; --i) {
        b[i] = path[i][s];
        s -= sta[ path[i][s] ];
    }
    for (int i = 1; i <= n; ++i) {
        printf("%d%c", b[i], " \n"[i == n]);
    }
}

int main() {
    int t = 1;
    while (t--) solve();
    return 0;
}

[CodeForces 453B] Little Pony and Harmony Chest

原文：https://www.cnblogs.com/Sstee1XD/p/14727561.html