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-24 18:18:36 on Problem 3017 and last updated at 2011-07-24 19:12:37
/*****************************************
f[i]表示前i个数分成若干份的最优解
g[i]表示最后一份从g[i]分到i
把第i + 1个数加进来,如果超过了m,从前面的数开始减,直到不大于m,设p为第p个数使得p到i + 1的总和不大于m
1.如果a[i + 1]小于max(g[i]到i中的最大值)且p大于等于g[i],f[i] = f[i - 1], g[i] = g[i - 1];
2.否则,f[i + 1] = min(f[j] + t) (p <= j <= i) t为j到i + 1中的最大数,此循环倒过来,方便计算t
Accepted	2516K	407MS	C++	693B
******************************************/
(>^ω^<)喵~~

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