HOJ::Problem : 192 - 撿肥皂

http://acoj.twbbs.org/blog_article.php?id=418
DP，狀態壓縮。

這題也是參考別人才寫出來的，以後要多練習自己想出來.....。
題目雖然說可以上下左右走，但是因為要不繞路，所以其實只能走右、下。首先因為有兩個人，DP狀態 DP[k][i][j] 代表走了k步後，第一個人的x座標是i，第二個人的x座標是j，(兩個人的y座標分別是 k-i,k-j，因為只能往下、右走)，並假設第二個人永遠比第一個人右邊，狀態轉移就是
if i==j  (兩個人走到同一格)
DP[k][i][j]= DP[k-1][i][j]  , DP[k-1][i-1][j] , DP[k-1][i-1][j-1]  這三個取max，加上這一格的權重D[k-i][i]。

if  i!=j (兩個人走到不同格)
DP[k][i][j]= DP[k-1][i][j]  , DP[k-1][i-1][j] , DP[k-1][i][j-1] , DP[k-1][i-1][j-1]  這四個取max，加上這兩個人走到的權重 D[k-i][i]+D[k-j][j]。

以上利用從左邊、上面走道這一格取max轉移，然後我把k壓掉，每次i,j從後面跑回來(不然順序會錯)，所以陣列只有二維。

第一次define for迴圈，感覺不錯，可是思考起來不太習慣，比賽還是好好寫for迴圈好了。

付上神人的題解：
http://chiangyo.blogspot.tw/2012/10/hoj-192.html