[UVa] 10036 - Divisibility

題目網址: http://goo.gl/SOLc0D

題意:給一長度為 n 的數列與一數 k，問在數列的相鄰兩數之間插入 '+' 或 '-' ，是否存在一運算法使得整個運算結果能夠被 k 整除。(1 <= n <= 10000, 2 <= k <= 100)



解法:由於 (a+b)%k = (a%k)+(b%k) ，所以運算後的結果只會介於 0 ~ k-1 ，用DP可以考慮所有的情況，複雜度O(n*k)。

遞迴方程 dp[i][v] =
          { true, i = 0 and v = 0
          { false, i = 0 and 0 < v < k
          { dp[i-1][(v-num[i])%k] || dp[i-1][(v+num[i])%k], i > 0 and 0 <= v <= k-1
表示 當考慮第 i 個數字後，mod k之後的值是否可能為v

TAG: DP

注意:

程式碼: