Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:膜拜奶牛英雄~很好的dp题~In Reply To:膜拜奶牛英雄~很好的dp题~ Posted by:rayafjyblue at 2011-07-21 15:45:43 > /******************************************* > 策略是1到n只牛轮流领跑,最后第n头牛踩线,跑了X圈的非头牛消耗的体力是X > dp[i][j][k] 表示第i只牛领跑,已经跑了j圈,头牛消耗的体力为k的状态下所耗最少时间 > 状态转移: > 1.仍然由第i头牛领跑,消耗一分钟,每分钟跑v圈,dp[i][j + v][k + v * v] = min(dp[i][j + v][k + v * v], dp[i][j][k] + 1); > 2.更换头牛,不消耗时间,此时已经跑过j圈的非头牛消耗的体力是j,dp[i + 1][j][j] = min(dp[i + 1][j][j], dp[i][j][k]); > ******************************************/ > (>^ω^<)喵~~ Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator