2015年2月16日 星期一

2015/02/16 vijos P1921 严厉的班长

// https://vijos.org/p/1921
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>

using namespace std;

#define INF 1e9

vector<int> prime;
bool is_prime[60];

int fac[60];

void find_prime()
{
    fill(is_prime, is_prime+60, true);
    is_prime[0] = is_prime[1] = false;

    prime.clear();

    for(int i = 2; i < 60; i++)
    {
        if( !is_prime[i] ) continue;

        prime.push_back(i);

        for(int j = i*i; j < 60; j += i)
            is_prime[j] = false;
    }
}

void set_fac()
{
    fill(fac, fac+60, 0);

    for(int i = 2; i < 60; i++)
        for(int vi = 0; vi < (int)prime.size(); vi++)
        {
            if( i%prime[vi] == 0 )
                fac[i] |= (1<<vi);
        }
}

int DP[200][1<<17];

int N;
int A[200];

int main()
{
    find_prime();
    set_fac();

    scanf("%d", &N);

    for(int Ni = 1; Ni <= N; Ni++)
        scanf("%d", &A[Ni]);

    fill(DP[0], DP[N]+(1<<17), INF);
    fill(DP[0], DP[0]+(1<<17), 0);

    for(int Ni = 1; Ni <= N; Ni++)
        for(int i = 1; i < 60; i++)
        {
            int p = (~fac[i]) & ( (1<<17)-1);

            for(int s = p; s; s = (s-1)&p)
            {
                int t = s|fac[i], d = abs(A[Ni]-i);
                DP[Ni][t] = min(DP[Ni][t], DP[Ni-1][s]+d);
            }
        }

    printf("%d\n", DP[N][(1<<17)-1]);
}

沒有留言:

張貼留言