(Codeforces) 623B. Array GCD

http://codeforces.com/problemset/problem/623/B

solution : http://codeforces.com/contest/623/submission/20172218

題目大意：給你一個長度n的序列(1<=n<=10^6)，裡面的每個值ai的範圍在[2,10^9]。現在，你可以做兩件事情：(1)刪除掉這個序列的 某個子序列(長度<=n-1) 這會花費a * m元，其中m是子序列的長度 (2)把序列的任意值 +1 or -1，把做一次這個動作，會花費b元。在你經過這兩件事情後，你會得到一個新的序列。題目的要求是：使得這個新序列的gcd值 >= 2。

可以注意到的一件事情是說：這個序列一定會包含 a1-1,a1,a1+1, an-1,an,an+1 的其中一個值(也就是說，開頭or尾巴 一定有一個可以留下來！)。因此，我們可以dp。一旦上面那六個值中的其中一個選定了，所擁有的質數有確定了！

假設我們擁有的質數是p，我們開三條dp陣列(dp[3][n])，其中dp[0][i]是指一路來在只有做     操作2 的情況下，前i個的最小cost，若無此case，則為INF。dp[1][i]是指在第i個把挖掉的情況下，前i個的最小cost。dp[2]則為在i之前已經刪除一段序列的情況下，前i個的最小值，若無此case，則為INF。 

我們先定義 "合法" ： 在經過操作後，得到的數字 % p == 0，其中p是上述中，選定的質數。

那麼，我們可以得到以下結論：

dp[0][i] = (如果合法)dp[0][i-1]+費用(沒有做操作2，就是0，其他情況就是b)
dp[1][i] = min( dp[0][i-1] + a, dp[1][i-1] + a)
dp[2][i] = min( (如果合法)dp[0][i-1] + 費用, dp[2][i-1] + 費用  )

如果有看不懂的話，歡迎在下面留言喔~