Solution
There is only one case to make product is a perfect square: For each number, the number of occurrences of prime factors is count[i]. if any different $i$, $j$ to make count[i]=count[j].
So for each number, the first thing is count the number of occurrences of prime factors. After hash with the count result, the problem turned into the problem: Segments, and each segment cannot have the same number.
Then define dp[i][j] as: The minimum number of segments required in first i number, and change at most j numbers. Now the question is how to calculate this dp.
Let's define left[i][j] as : The farthest position you can go to the left from the ith number, and change at most j numbers, and no perfect square. Then the dp[i][j] = min(dp[left[i][j-x] - 1][x] + 1).
Which means for we split the question to two part, the first part is (1, left[i][j-x] -1), which we at most change x numbers. The second part is (left[i][j-x] - 1, i), which is a single segment (refer to the definition of left).
About how to calculate left. let's define pre[i] as: the first duplicate number before ith number. Now scan the array from begin to end, when we found pre[i] is not empty, we put the pre[i] into a priority queue. When we found the size of priority queue is more than j, then we pop up the smallest pre[k]. Then left[i][j] = pre[k] + 1.
Code
