本文主要是介绍CodeForces 453B Little Pony and Harmony Chest，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接~~>
做题感悟：本来想水道简单题来，结果这题竟然是状态压缩，想到了分解素因子的方法但是没有想到用状态压缩，因为一看 n 就没状态压缩的想法了，可能状态压缩太弱啊!
解题思路：
因为 ai 不大于 30 ，每个位置都可以放置 1 ，so ~ > bi 应该小于 59 ，因为如果 ai = 30 ,放置 放 1 和放59 是一样的 30 -1 = 59 - 30 所以B数列的数的范围也就确定了，因为B数列的数两两互质，如果用gcd 必定不行，这里可以查看任意两个数是否有素因子，如果有说明不互质，否则互质。从 1 ~ 58 只有16 个素数用状态压缩完全可以，每一位表示一个素数是否存在，然后递推一下就可以了，输出时递归输出即可。
代码：
#include<iostream>
#include<fstream>
#include<iomanip>
#include<ctime>
#include<fstream>
#include<sstream>
#include<stack>
#include<cstring>
#include<map>
#include<vector>
#include<cstdio>
#include<algorithm>
#define INT __int64
using namespace std ;
const int INF = 1000000000 ;
const int MY = 59 ;
const int MX = 100 + 10 ;
int num ,n ;
bool flag ;
int prime[MX] ,key[MX] ,g[MX] ,dp[MX][1<<(16)] ;
bool is_prime[MX] ;
void init() // 预处理
{num = 0 ;memset(is_prime ,false ,sizeof(is_prime)) ;for(int i = 2 ;i < MY ;i++){if(!is_prime[i]) prime[num++] = i ;for(int j = 0 ;j < num && prime[j]*i<MY ;j++){is_prime[i*prime[j]] = true ;if(i%prime[j] == 0)break ;}}key[1] = 0 ;for(int i = 2 ;i < MY ;i++){int K = 0 ;for(int j = 0 ;j < num ;j++){if(i%prime[j] == 0)K |= (1<<j) ;if(i < prime[j]) break ;}key[i] = K ;}
}
void print(int x ,int S) // 递归输出
{if(!x) return ;for(int i = 1 ;i < 59 ;i++)if((S &key[i])==key[i] && dp[x][S] == dp[x-1][S^key[i]] + abs(i - g[x]) && dp[x-1][S^key[i]] != -1){print(x-1 ,S^key[i]) ;if(flag){ cout<<i ; flag =false ; }else cout<<" "<<i ;break ;}
}
void DP()
{int ans = INF ;memset(dp ,-1 ,sizeof(dp)) ;dp[0][0] = 0 ;for(int i = 1 ;i <= n ;i++)for(int S = (1<<16)-1 ;S >= 0 ;S--)for(int j = 1 ;j < 59 ;j++)if(dp[i-1][S] != -1 && !(S & key[j])){if(dp[i][S|key[j]] != -1)dp[i][S|key[j]] = min(dp[i][S|key[j]] ,dp[i-1][S] + abs(j-g[i])) ;else dp[i][S|key[j]] = dp[i-1][S] + abs(j-g[i]) ;if(i == n)ans = min(ans ,dp[i][S|key[j]]) ;}for(int i = 0 ;i < (1<<16) ;i++)if(dp[n][i] == ans){flag = true ;print(n ,i) ;break ;}cout<<endl ;
}
int main()
{init() ;while(~scanf("%d",&n)){for(int i = 1 ;i <= n ;i++)scanf("%d",&g[i]) ;DP() ;}return 0 ;
}
这篇关于CodeForces 453B Little Pony and Harmony Chest的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
