[CF453B]Little Pony and Harmony Chest

题目大意：

给你一个长度为\(n(n\le100)\)的正整数序列\(A(A_i\le30)\)，求一个正整数序列\(B\)，使得\(\sum_{i=1}^n |A_i-B_i|\)最小，且\(B\)中所有互质。

思路：

由于\(B_i\ge59\)时用\(1\)代替时不会更差，因此我们只需要考虑\(B_i\le58\)的情况。由于质因数只有\(16\)个，因此可以状压DP。另外记录转移即可。

源代码：

#include
#include
#include
#include
inline int getint() {register char ch;while(!isdigit(ch=getchar()));register int x=ch^'0';while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');return x;
}
typedef long long int64;
const int p[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};
const int N=101,P=16,B=59,S=1<=1;i--) {b[i]=g[i][last];last^=s[g[i][last]];}for(register int i=1;i<=n;i++) {printf("%d%c",b[i]," \n"[i==n]);}return 0;
}

转载于:https://www.cnblogs.com/skylee03/p/10070457.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！