摘要: 首先明確一點：最優(yōu)解必為奶牛1..n-1輪流領跑，奶牛n撞線。且跑了x圈后，未領跑過的奶牛都耗費了x的體力。
設f[i][j][k]表示前i-1頭奶牛已領跑，現(xiàn)在由第i頭奶牛領跑，一共跑了j圈，奶牛i耗費了k的體力。
則f[i][j][k]可以轉移到f[i][j + p][k + p^2]（耗費1分鐘，奶牛i以p圈/分鐘的速度繼續(xù)領跑），也可轉移到f[i + 1][j][j]（換成奶牛i + 1領跑，不耗費時間）。
時間復雜度為O(nde^2.5)。
閱讀全文