傳智播客的課表上按順序提供 n 節(jié)課程,課程可能是 Java、Python 或者前端開發(fā)等等,我們用不超過 n 的正數(shù)代表每一節(jié)課程的種類。學(xué)員可以從這個課程序列選取連續(xù)的一小段的課程序列,作為一周的學(xué)習(xí)任務(wù)。
為了使學(xué)習(xí)任務(wù)不那么枯燥,學(xué)員不想連續(xù)上兩節(jié)相同的課。特殊的,這一周學(xué)習(xí)任務(wù)的開頭和結(jié)尾也不能是相同的課。為了保證學(xué)習(xí)效果,一周內(nèi)至少要學(xué)完 l 節(jié)課程。
請問,我們有多少種合法的選課方案?
兩種選課方案,只要選取的課程序列在原序列的開頭和結(jié)尾有至少一個位置不一致,那么就可以認(rèn)為是不同的選課方案。注意,即使 l 是 1,一周只安排一次課也是不合法的,至少需要安排 2 次課。
每個測試點由多組數(shù)據(jù)組成。
第一行為一個整數(shù) T,代表數(shù)據(jù)的組數(shù)。
對于每組數(shù)據(jù),第一行輸入兩個正整數(shù) n 和 l。接下來一行輸入 n 個非負(fù)整數(shù) c_i 表示課程種類編號。
2 3 1 1 2 3 5 3 1 2 3 1 1
3 2
對于第一組數(shù)據(jù),有 [1,2] 和 [2,3] 和 [1,2,3] 三種方法。
對于第二組數(shù)據(jù),由于至少要選 3 門課,只有 [1,2,3] 和 [2,3,1] 兩種方法。
比賽前十名將獲得又傳智官方提供的書籍獎勵
大家可以登錄http://www.ityxb.com/originalBook/Java隨意選擇,私信書名+地址給驗題君,否則隨機(jī)發(fā)哦!
比賽結(jié)束后,博客發(fā)布傳智杯完整題目題解的同學(xué)將贈送程序員小罐茶一份,限定三個名額!
PS:請大家務(wù)必完善個人聯(lián)系信息用于收獎品哦