题意：
给你一个长度为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
