在講這題之前呢,先來講一個新概念,差分約束系統。

"如果一個系統由n個變數和m個約束條件組成,其中每個約束條件形如xj-xi<=bk(i,j∈[1,n],k∈[1,m]),則稱其為差分約束系統(system of difference constraints)。

亦即,差分約束系統是求解關於一組變數的特殊不等式組的方法。"

"求解差分約束系統,可以轉化成圖論的單源最短路徑問題。觀察xj-xi<=bk,會發現它類似最短路中的三角不等式d[v] <=d[u]+w[u,v],即d[v]-d[u]<=w[u,v]。

因此,以每個變數xi為結點,對於約束條件xj-xi<=bk,連接一條邊(i,j),邊權為bk。再增加一個原點(s,s)與所有定點相連,邊權均為0。"

先來定義一個東西,f[i] = 0~i-1最少有幾個整數。

對於這一題呢,有以下兩種不等式:

(1) 題目的 a, b, c 表 a~b之中有至少c個整數。

得以下關係式,f[b+1]>=f[a]+c。

(2) 滿足整數性質。

-> 0 <= f[i]-f[i-1] <= 1

-> f[i+1]>=f[i]+0 & f[i]>=f[i+1]-1

有以上這兩條不等式,即構成一差分約束系統。

即可用 最短路 求解。

我的code

http://codepad.org/hjDNVKNO

p.s 因為 Hsiao-Bao 表示 POJ 有些題會卡 vector ,所以就改成 linked_list。

      雖然沒有 指標 那麼漂亮,但還是蠻好寫的,有興趣的人可以參考一下。

文章標籤
創作者介紹

jghs1328

jghs1328 發表在 痞客邦 PIXNET 留言(0) 人氣()