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

优质dp留爪~

Posted by rayafjyblue at 2011-07-21 20:22:08 on Problem 1821
/************************************************
dp[i]表示粉刷前i个栅栏最大价值
dp[i] = max(dp[j] + len * cost); 复杂度为O(k * n * n),需优化
枚举工人i,递减枚举第i个工人的右边界,定义k = p[i],表示第i个工人的左边界
dp[j] = max(dp[k - 1] + (j - k + 1) * cost[i]); 维护k
定义j为递减枚举的右边界, t = j - len[i] + 1, 当((k - 1) - (t - 1)) * cost[i] > dp[k - 1] - dp[t - 1]时,更新k = t;
************************************************/

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