Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:膜拜奶牛英雄~很好的dp题~

Posted by MrLuoTrue at 2020-12-16 09:06:53 on Problem 1946
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator