https://codeforces.com/problemset/problem/454/D
给n个数ai,
(
1
≤
n
≤
100
)
(1 \leq n \leq 100 )
(1≤n≤100)
(
1
≤
a
i
≤
30
)
(1 \leq a_i \leq 30 )
(1≤ai≤30)
把他们变成n个数bi,使得:
1:
∑
i
=
1
n
a
b
s
(
a
i
−
b
i
)
\sum_{i=1}^nabs(a_i - b_i)
∑i=1nabs(ai−bi)最小
2:
g
c
d
(
b
i
,
b
j
)
=
1
gcd(b_i,b_j) = 1
gcd(bi,bj)=1
求取bi的一组可行解
想了半天没想出来,请教 @Jerry99s 大佬才略明白一点,果然我dp还是菜啊。。
首先明确:
1.b数组中任意两数的 质因子集合 没有交集。 (由gcd==1 得来)
2.b数组中不会有数超过60。 (
a
i
≤
30
a_i\leq30
ai≤30,变到60以及以上,莫不如变到1,因为1的质因子集合为空,和谁的交集都是空)
60以内一共17个质数,所以60以内的数的质因子集合,以及这些集合的并集 可以用(1<<17)个状态表示。
设dp[
n
i
d
nid
nid][
b
i
n
_
s
t
bin\_st
bin_st]为 取前
n
i
d
nid
nid个数
a
i
a_i
ai,将他们变成
b
i
b_i
bi后
b
i
b_i
bi的质因子集合为
b
i
n
_
s
t
bin\_st
bin_st
则有以下转移(cval表示bi的值,son[i]表示i的质因子集合):
d
p
[
n
i
d
]
[
b
i
n
_
s
t
]
=
m
i
n
(
i
t
s
e
l
f
,
d
p
[
n
i
d
−
1
]
[
b
i
n
_
s
t
⊕
s
o
n
[
c
v
a
l
]
]
+
a
b
s
(
a
[
n
i
d
]
−
c
v
a
l
)
)
(
前
提
:
s
o
n
[
c
v
a
l
]
⊆
b
i
n
_
s
t
)
dp[nid][bin\_st] =min( itself, dp[nid-1][bin\_st \oplus son[cval]] + abs(a[nid]-cval))\\ (前提:son[cval] \subseteq bin\_st )
dp[nid][bin_st]=min(itself,dp[nid−1][bin_st⊕son[cval]]+abs(a[nid]−cval))(前提:son[cval]⊆bin_st)
通俗来讲,状态是取了前nid个数,形成了集合bin_st,
我们取任意1-60的数cval和一个包含它的因子集合bin_st,都可以尝试将状态转移。
转移方法就是先把cval的质因子从bin_st中扣除去,形成前驱集合tmp,这样的话
前nid-1个数,形成tmp集合的状态
就可以转移到
前nid个数,形成bin_st集合的状态
取最小代价即可。
那么bi咋求呢?转移时记录一下cval就好,最后可以倒着由最优解对应的集合一层一层剥出来
每次成功转移时,将cval记录到rans[nid][bin_st] ,也就是说,修改完第nid个数,总体因子集合到bin_st状态时,我们将第nid个数修改成的值是cval。
这样找出最后一层后,把最后一个数的因子从集合里抠出来,接着找倒数第二层…最后倒着输出即可。
(再想想就可以优化个常数,比如59不可取)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 105;
const int MAXB = 140000;
const int INF = 0x3f3f3f3f;
int nums[MAXN];
int dp[MAXN][MAXB];
int rans[MAXN][MAXB];
int top = (1<<16);
int pr[20] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53}; //16个
int son[MAXN];
int print[MAXN];
void init() {
for(int i=1; i<54; i++) {
for(int j=0; j<16; j++) {
if(i%pr[j]==0) son[i] |= (1<<j);
}
}
}
int main() {
init();
int n;
cin>>n;
for(int i = 1; i <= n; i++){
scanf("%d",&nums[i]);
}
memset(dp,0x3f,sizeof(dp));
dp[0][0] = 0;
for(int nid = 1; nid <= n; nid++) {
for(int bin_st = 0; bin_st < top; bin_st++) {//后来觉得这层应该反过来写
for(int cval = 1; cval < 54; cval++) {
if((bin_st & son[cval]) != son[cval]) continue;//要么这句就有点丑。。。
if(dp[nid][bin_st] > dp[nid-1][bin_st^son[cval]] + abs(nums[nid]-cval)) {
dp[nid][bin_st] = dp[nid-1][bin_st^son[cval]] + abs(nums[nid]-cval);
rans[nid][bin_st] = cval;
}
}
}
}
int ans = INF,num = 0;
for(int bin_st = 0; bin_st < top; bin_st++ ){
if(ans > dp[n][bin_st]) {
ans = dp[n][bin_st];
num = bin_st;
}
}
for(int nid = n; nid >= 1; nid--) {
print[nid] = rans[nid][num];
num = num ^ son[print[nid]];
}
for(int i = 1; i <= n; i++){
printf("%d ",print[i]);
}
return 0;
}
才疏学浅,如有错误,欢迎指正。