[Day6]B 君的第三题 (shenyang)

题目大意

给你一个长度为n的数组,你需要更改里面各项的值使得它们两两互质。
代价为改后数字与原始值的差值的绝对值。求最小代价。

题解

这个题解算是在分享做题的心路历程,比较磨叽,可以只看黑体字部分

一开始都已经弃疗了(别一开始就放弃啊喂!)准备打一个暴力骗点分……
于是就打算枚举每一项,对于每一项枚举每一个可能值。
枚举值肯定有范围的,不能可在int范围内枚举吧。
于是就发现了:
结论1:改后的数的范围在[1,59]之间
下界是题目给的,我们只对上界进行讨论
证明:我们设数列为A_1,A_2,\cdots A_n,由于题目中A_i\le30,且1与任意自然数互质。因此|A_i-1|\le|A_i-59||A_i-1|<|A_i-59|。因此改后的数的上界为59。

找到了范围就可以开心地枚举啦!!理论上O(59^n)n=4的时候过不了。但实际上可以很多情况下可以提前判断不互质而提前退出,因此30pt到手!

很自然地去想如何判断不互质——有相同的质因子

每次都去算质因子好麻烦,而且数字很小,于是就可以开一个数组zz[i]存i的质因子,我们发现60以内的质数只有17个,可以直接用状态存

都写到这了还写什么暴力orz,直接上状压啊!

状态设计↓
我们设计d[i][j]表示第i个数,在状态j(有多少个质因子)下,所耗费的最小费用。
初始化d数组为\infty,d[0][0]=0
现在需要枚举每个可以转移的合法状态,设初始时fzz=((1<<17)-1)\ xor\ zz[j],该项原始值为a
状态转移方程为:
d[i][fzz|zz[j]]=min(d[i-1][fzz]+abs(a-j))
最后min(d[n][i])就是答案

代码

发表评论

电子邮件地址不会被公开。 必填项已用*标注