http://acm.hdu.edu.cn/showproblem.php?pid=1500這題目和般寢室其實是類似的
http://acm.hdu.edu.cn/showproblem.php?pid=1421不過多加了一個條件，后邊還要有一根筷子
所以就不能到DP到n
要根據每次取的筷子數
算出一個max值
DP到這個max值就可以了。
max~n的值就不用dp了
其實再優化一下max~max+3就行了
由于數組很大，1000*5000的，我開了一個2*5000的滾動數組，這是我第一次用滾動數組
用異或運算很容易實現
下邊的是狀態轉移方程
for(i++;i<=max;i++)
dp[next][i] = Min(dp[next][i-1],dp[row][i-2] + (cho[i] - cho[i-1])*(cho[i] - cho[i-1]););
for(i=max+1;i<=max+3;i++)
dp[next][i] = dp[next][i-1];
posted on 2009-02-20 11:28
shǎ崽 閱讀(396)
評論(0) 編輯 收藏 引用