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的做法吧?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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator