Felicia

2007年9月1日

[动态规划]pku1946
     摘要: 首先明确一点：最优解必为奶牛1..n-1轮流领跑，奶牛n撞线。且跑了x圈后，未领跑过的奶牛都耗费了x的体力。
设f[i][j][k]表示前i-1头奶牛已领跑，现在由第i头奶牛领跑，一共跑了j圈，奶牛i耗费了k的体力。
则f[i][j][k]可以转移到f[i][j + p][k + p^2]（耗费1分钟，奶牛i以p圈/分钟的速度继续领跑），也可转移到f[i + 1][j][j]（换成奶牛i + 1领跑，不耗费时间）。
时间复杂度为O(nde^2.5)。

  阅读全文
posted @ 2007-09-01 11:42 Felicia 阅读(479) | 评论 (1) | 编辑 收藏
 
Powered by:
C++博客
Copyright © Felicia