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 |
优质dp留爪~/************************************************ 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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator