codeforces 454 D. Little Pony and Harmony Chest（状压dp）

题目链接：http://codeforces.com/contest/454/problem/D

题意：给定一个序列a， 求一序列b，要求∑|ai−bi|最小。并且b中任意两数的最大公约数为1.

题解：首先要满足最大公约数为1只要控制b中的最小素因数就行。由于a最大之后30，所以加的数肯定不会超过60

如果超过了，直接选择1更小，然后1～60内最多只有17个素数，所以最多状态就是1<<17于是可以考虑一下状压

dp，dp[i][s]表示前i个数拥有素因数的状态为s，然后是转移

x = stat[k] | j 。stat[k]表示的是（k属于1～60.）选择k的限制条件，如果stat[k]&j ！=0就跳过。

#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <cmath>
#define inf 0X3f3f3f3f
using namespace std;
const int M = 1e2 + 10;
int prime[] = {2,3,5,7,11,13,17,19,23,29,31,37,39,41,43,47,53};
int a[M] , dp[M][1 << 17] , stat[61] , num[M][1 << 17] , pre[M][1 << 17] , b[M];
int main() {
    int n;
    scanf("%d" , &n);
    for(int i = 1 ; i <= n ; i++) {
        scanf("%d" , &a[i]);
    }
    memset(stat , 0 , sizeof(stat));
    for(int i = 2 ; i <= 60 ; i++) {
        for(int j = 0 ; j < 17 ; j++) {
            if(!(i % prime[j])) stat[i] |= (1 << j);
        }
    }
    memset(dp , inf , sizeof(dp));
    dp[0][0] = 0;
    for(int i = 0 ; i < n ; i++) {
        for(int j = 0 ; j < (1 << 17) ; j++) {
            if(dp[i][j] == inf) continue;
            for(int k = 1 ; k <= 60 ; k++) {
                if(stat[k] & j) continue;
                int x = (stat[k] | j);
                if(dp[i][j] + abs(a[i + 1] - k) < dp[i + 1][x]) {
                    dp[i + 1][x] = dp[i][j] + abs(a[i + 1] - k);
                    num[i + 1][x] = k;
                    pre[i + 1][x] = j;
                }
            }
        }
    }
    int MIN = inf , pos = 0;
    for(int i = 0 ; i < (1 << 17) ; i++) {
        if(MIN > dp[n][i]) {MIN = dp[n][i] , pos = i;}
    }
    for(int i = n ; i >= 1 ; i--) {
        b[i] = num[i][pos];
        pos = pre[i][pos];
    }
    for(int i = 1 ; i <= n ; i++) {
        printf("%d " , b[i]);
    }
    printf("
");
    return 0;
}