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留爪~提供一种无需任何数据结构优化的菜鸟写法……不知道是否是数据太弱的关系……/***************************************** 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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator