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

这道题可以从数学的角度加以简化,思想还是贪心

Posted by Ontheline at 2009-04-08 18:39:26 on Problem 2586
共有12个月,记为x1,x2,x3,....,x12
1)考虑每五个一组:
x1,x2,x3,x4,x5
   x2,x3,x4,x5,x6
      x3,x4,x5,x6,x7
.....................
                    x8,x9,x10,x11,x12;
第i组一定要满足,最大的组合k(这里的k表示有k个月是盈利的,例如k=3,表示sssdd)
这里体现了贪心的思想.
2)对于同样是k的组合,配列有很多种,用组合数表示,应该是5!/k!*(5-k)!如果全部考虑是不行的.
从1)中我们可以推出x1x2x3x4x5=x6x7x8x9x10,所以在满足1)的条件下只要x11x12尽量是s就可以了.如果k>2,这样总是可以x11x12=ss总是可以满足的.如果k<=2,那么就尽量在剩下的两个月中满足k的组合就好了,这样做就能保证盈利最大,如果这个最大值仍为<=0的数,那么就输出Deficit

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