從中點(diǎn)出發(fā)，到達(dá)左右的所有地方，最后回到終點(diǎn)的中點(diǎn)。

動態(tài)規(guī)劃，注意初始化，計算浮點(diǎn)數(shù)時的問題

?從中點(diǎn)出發(fā)，到達(dá)左右的所有地方，最后回到終點(diǎn)的中點(diǎn)。

?

動態(tài)規(guī)劃，注意初始化，計算浮點(diǎn)數(shù)時的問題

定義：dp[i][j][k]表示處理到左邊第i個，右邊第j個，當(dāng)前位置在k的情況。k只有2個值，0為在左，1為在右。

狀態(tài)轉(zhuǎn)移:

????????1、處理dp[i][j][0]： 此時狀態(tài)的含義：1、在左邊 2、i是即將要處理的?。3、j位置已經(jīng)處理過了。 只能從左邊下面一個轉(zhuǎn)移過來，或者是從右邊橫過來（從已處理的狀態(tài)轉(zhuǎn)移過來）；但注意，不可能從右下或者是右上過來。從dp的定義看，是【已處理】，如果右下過來，就不算是處理到第j個了；對于后者，表象考慮的其實(shí)是右邊走的快再轉(zhuǎn)到左邊的情況，但實(shí)際上，因?yàn)閖在第二層for，所以對于左邊的一個點(diǎn)i，實(shí)際上是從右邊所有的點(diǎn)（all j）轉(zhuǎn)移過來的，在此基礎(chǔ)上取最值。即保證了所有情況都已經(jīng)被處理，單個選擇最優(yōu)，總體必為最優(yōu)

????????2、處理dp[i][j][1]：相同

????????3、初始化：單邊走，不從另一邊走過來的情況下總的距離；第一個點(diǎn)需要進(jìn)行sqrt（a*a+b*b）；同時，當(dāng)前位置的另一邊應(yīng)是無效狀態(tài)，要把其改為0x3f3f3f3f。同時因?yàn)閣要除以2，要么在一開始讀值的時候保證w是double，要么在計算的時候進(jìn)行手動強(qiáng)轉(zhuǎn)，否則不準(zhǔn)。

總代碼：