http://codeforces.com/problemset/problem/453/B
cf机子跑的真快,4亿的复杂度都可以跑过,最多也就1s多,给的4s
当时写的时候不太敢写,觉得4e8了==,况且自己还要递归打印
于是各种优化,300多ms就跑完了,给的4s
dp[i][j]
前i个数,对应的所存在的素数的状态为j时,差值的最小值 (对应的b序列最多是1到58,就是16个素数,二进制表示,每个素数的存在,1<<16)
优化1:
当n大于16时,一定会有n-16个1,因为最多有16个互质的数,剩下的就只能是1了
贪心一下,先排序,从大到小,每个对应的ai,初始化为1
只需处理前16个ai,所以n的范围就缩小为1到16
n = min(16,n)
优化2:
下一个bi一定不能存在约数,与素数状态为j时,其中的素数不互质
ans[i][j]:状态为i时,b为j
ans[i][j]=-1代表素数不互质,否则储存加进j后的状态t
优化3:
dp[i][k]是由dp[i-1][t]的状态转化来的,dp[i-1][t]必须存在才行
即dp[i-1][t]!=inf
最后递归打印就好了
代码如下
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <climits>
#include <string>
#include <vector>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <sstream>
#include <cctype>
using namespace std;
typedef long long ll;
typedef pair<int ,int> pii;
#define MEM(a,b) memset(a,b,sizeof a)
#define CLR(a) memset(a,0,sizeof a);
const int inf = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
//#define LOCAL
struct node
{
int pos;
int x;
int y;
}a[101];
int ans[1<<17][60];
int dp[20][1<<17];
int v[40];
int vis[100];
int cnt = 0;
int n=16;
bool cmp(node a,node b){
return a.x > b.x;
}
void init(){
for(int i=0;i<(1<<16);i++){
for(int j=1;j<=59;j++){
int t = i;
int flag = 1;
for(int k=0;k<cnt;k++){
if((i & (1<<k)) && j%v[k]==0){
ans[i][j]=-1;
flag = 0;
break;
}
else if(j%v[k]==0){
t |= (1<<k);
}
}
if(flag){
ans[i][j]=t;
}
}
}
}
void dfs(int l,int x,int nmin){
if(l==0)return ;
int res = 1;
for(int i=0;i<(1<<16);i++){
for(int j=1;j<=59;j++){
if(ans[i][j]==x && dp[l-1][i]+fabs(j-a[l].x)==nmin){
dfs(l-1,i,dp[l-1][i]);
res = j;
goto end;
}
}
}
end:
a[l].y = res;
return;
}
int main()
{
#ifdef LOCAL
freopen("in.txt", "r", stdin);
// freopen("out.txt","w",stdout);
#endif
for(int i=2;i<=58;i++){
if(!vis[i]){
v[cnt++]=i;
for(int j=i*2;j<=58;j+=i){
vis[j]=1;
}
}
}
init();
int N;scanf("%d",&N);
for(int i=1;i<=N;i++){
scanf("%d",&a[i].x);
a[i].pos = i,a[i].y = 1;
}
sort(a+1,a+1+N,cmp);
n = min(n,N);
MEM(dp,inf);
dp[0][0]=0;
for(int i=1;i<=n;i++){
for(int j=0;j<(1<<16);j++){
if(dp[i-1][j]!=inf){
for(int k=1;k<=59;k++){
if(ans[j][k]!=-1){
dp[i][ans[j][k]]=min(dp[i][ans[j][k]],dp[i-1][j]+(int)fabs(k-a[i].x));
}
}
}
}
}
int ans = inf;
int x;
for(int j=0;j<(1<<16);j++){
if(ans > dp[n][j]){
ans = dp[n][j];
x = j;
}
}
dfs(n,x,ans);
for(int i=1;i<=N;i++){
for(int j=1;j<=N;j++){
if(i==a[j].pos){
printf("%d ",a[j].y);
}
}
}
return 0;
}