Welcome To SDIBT ACM-ICPC Online Judge

VIRTUAL JUDGE Recent Contest F.A.Qs Discuss Home ProblemSet Status Ranklist 2 Contest LoginRegister Exam
SDIBT Online Judge WebBoard
[ New Thread ]
Problem 2368 >> 最长下降子序列
wl10174102 @ 2013-07-30 17:08:33
[ Quote ] [ Edit ] [ Delete ] 1#
1、用num[i]表示第i个数
2、用len[i]表示以i为尾的下降子序列的最大长度【len[i]=MAX(len[j])+1,1<=j<i,num[j]>num[i]】
3、用cnt[i]表示以i位尾的最长下降子序列的个数【cnt[i]+=cnt[j],1<=j<i,len[i]==len[j]+1,num[j]>num[i]】
4、最后找出所有最长下降子序列的个数和
【注意判重】
(1)计算cnt[i]时,若j在i之前已出现过,则忽略
(2)计算各cnt[i]和时,若j出现过,则忽略
【注意高精度】
用数组表示,也即小大数
【Bug】
为啥我用next[i]值记录在num[i]值之后与num[i]值相等的值的下标,然后在判重中不再重复查找,却WA呢~~
[Top]  [Previous]  [Next]

HOME Back

한국어 中文 English
All Copyright Reserved 2008-2010 SDIBT TEAM
GPL2.0 2003-2010 HUSTOJ Project TEAM
Anything about the Problems, Please Contact Admin:admin