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快,数据好弱! 讲讲DP的做法吧?

Posted by sunmoonstar_love at 2005-07-07 20:47:32 on Problem 1014
In Reply To:这样做可以吗??? Posted by:me at 2005-07-05 17:17:04
> 请各路高手帮忙看一下,这样做行不行,WA了N多次了。
> 
> 输入为数列C
>   n=C1+C2*2+C3*3+C4*4+C5*5+C6*6
>   如果n为奇,则不可平分
>   否则
>     先将原数列C分给数列A和数列B,分的方法如下:
>       从C6开始,如果A的总value—VA大于B的总value—VB,
>                 则A6++,C6--,否则B6++,C6--,直到把C6=0;
>       对C5,C4,C3,C2,C1也如此操作。
>     分完后,算出A,B的差T,T为偶数且T<7(应该是吧),
>     对A,B,T作如下判断(设VA>=VB):
>       T=0:可平分;
> 
>       T=6:不可平分;
> 
>       T=4:如果存在1组Ai>0,B[i-2]>0,则Ai--,Bi++,即平分了,
>             如果存在1组Ai>1,B[i-1]>1,则Ai-=2,Bi+=2,即平分了,
>             如果存在2组Ai>0,B[i-1]>0,则Ai--,Bi++,即平分了,
>             否则不可平分;
> 
>       T=2:如果存在1组Ai>0,B[i-1]>0,则Ai--,Bi++,即平分了,
>             否则不可平分;
> (判断其实是为了看是否能通过对调A,B的1对或2对数,使VA=VB,
>   例如A=0 0 1 1 1 0
>       B=0 0 0 1 0 1
>       T=2
>       则可通过A给B一个5,B给A一个4,得
>       A=0 0 1 2 0 0
>       B=0 0 0 0 1 1
>       即平分了。)

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