Codeforces Round #708 Square-free division DP

题意:

给你一个长度为n的数组a。要对数组a进行分段,每一段里面,任意两个数$a_i$,和$a_j$的乘积不能是整数的平方。现在给你一个k,表示你可以把数组中k个数改成任意正整数。问你改完之后最小需要分成几段。

题解:

我太菜了。硬是没想到直接往前找最远可以放在一段的然后分k。最后看的题解。

首先,乘积是平方数只有一个可能:他们的素因数中,出现奇数次的素因数一致。因此对于任意数,第一件事情就是换成那些出现奇数次素因数的乘积。于是问题转化成了,分段,且每段不能有相同的数。

那么dp[i][j]表示,到i为止,改j个数,最少需要分几段,其实是一个自然的想法。我其实也想到了这一层。问题是怎么维护这个dp呢?显然,自然的想法是,找i-?和j-?推过来咯。到这我就确实没想到了。

其实就很简单,维护一个left[i][j]。表示以i结尾,改j个数,然后往左最远可以走到的位置。于是dp[i][j] = min(dp[left[i][j-x] - 1][x] + 1)。意思就是说,我dp[i][j]的话,首先看以i结尾改x个能到哪里。然后改了x个剩下的,问上一个位置的dp结果。

至于left的维护。我个人是直接维护了一个pre[i]。pre[i]表示第i个数往左最近一个重复数字的位置。对于固定的j。每次从左往右扫一次,扫到pre[i]有值的就扔进优先队列里。当发现优先队列长度超过j了,就把最小的(也就是最左边的一个重复数字)pop出来。然后保留这个pop出来数字右边第一个作为left[i][j]的值。

代码:

Submission #111585214 - Codeforces
Codeforces. Programming competitions and contests, programming community
展示评论