pku1205 Water Treatment Plants 遞推（說(shuō)DP也可以把。。）

題意：
一個(gè)污水處理系統(tǒng)嗎，n個(gè)城市，每個(gè)城市可以選擇
1、將左邊城市過(guò)來(lái)的污水和右邊城市過(guò)來(lái)的污水連同本身的污水排到河里
2、將左邊來(lái)的污水連同自己的污水排到右邊
3、將右邊來(lái)的污水連同自己的污水排到左邊


解法：
設(shè)狀態(tài)dp[i][0]為第i個(gè)城市選擇將污水傳到左邊的方案數(shù)，dp[i][1]為第i個(gè)城市選擇將污水排入河道的方案數(shù)，dp[i][2]為選擇將污水排到右邊城市的方案數(shù)
然后有遞推式
dp[i][2]=dp[i][1]=sum(dp[i-1][j]),j=0,1,2
dp[i][0]=dp[i-1][0]+dp[i-1][1]
這個(gè)應(yīng)該不難理解吧？
如果最后一個(gè)城市選擇后兩種方案，那么前面城市怎么連都無(wú)所謂
而最后一個(gè)城市選擇第一個(gè)方案，那么第n-1個(gè)城市不能選擇將污水排到第n個(gè)城市
注意初始條件，dp[1][0]=0,dp[1][1]=dp[1][2]=1;
然后就是java  BigInteger ，嘻嘻

posted on 2011-01-15 17:22 yzhw 閱讀(218) 評(píng)論(0)  編輯 收藏 引用 所屬分類: DP