http://acm.hdu.edu.cn/showproblem.php?pid=1500這題目和般寢室其實(shí)是類似的
http://acm.hdu.edu.cn/showproblem.php?pid=1421不過多加了一個條件，后邊還要有一根筷子
所以就不能到DP到n
要根據(jù)每次取的筷子數(shù)
算出一個max值
DP到這個max值就可以了。
max~n的值就不用dp了
其實(shí)再優(yōu)化一下max~max+3就行了
由于數(shù)組很大，1000*5000的，我開了一個2*5000的滾動數(shù)組，這是我第一次用滾動數(shù)組
用異或運(yùn)算很容易實(shí)現(xiàn)
下邊的是狀態(tài)轉(zhuǎn)移方程
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ǎ崽 閱讀(386)
評論(0) 編輯 收藏 引用