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

发布于 2019-01-30  100 次阅读


题目大意

给你一个长度为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])$就是答案

代码


哇,你居然发现了这里!