IwfWcf's OI Log: Vijos 1421 更换轮胎解题报告

2009年2月13日星期五

Vijos 1421 更换轮胎解题报告

用f[i,j]表示第i圈用第j种轮胎完成所需要的最少时间，用minl表示完成上一圈所需的最少时间，则易得状态转移方程：f[i,j]:=min(f[i-1,j],minl+c)+t[i,j];

如果一边读入一边DP并且使用滚动数组优化可以将空间复杂度降到O(n)。

R1144131 Accepted 100 From IwfWcf－ P1421 FPC Vivid Puppy 2009-2-13 13:13:51

没有评论:

发表评论

订阅：博文评论 (Atom)

Creative Commons License

除非另有声明，本网站采用知识共享署名-非商业性使用-相同方式共享 3.0 许可协议授权。