一、編程題(共4題，每題25分，共100分)1.數(shù)字三角形問(wèn)題

試題編號(hào)：試題類(lèi)型：編程題標(biāo)準(zhǔn)答案：試題難度：一般試題解析：展示地址：點(diǎn)擊瀏覽數(shù)字三角形問(wèn)題738810274445265(圖1)圖1給出了一個(gè)數(shù)字三角形。從三角形的頂部到底部有很多條不同的路徑。對(duì)于每條路徑，把路徑上面的數(shù)加起來(lái)可以得到一個(gè)和，你的任務(wù)就是找到最大的和。注意：路徑上的每一步只能從一個(gè)數(shù)走到下一層上和它最近的左邊的那個(gè)數(shù)或者右邊的那個(gè)數(shù)。時(shí)間限制：1000內(nèi)存限制：65536輸入輸入的是一行是一個(gè)整數(shù)N(1<N<=100)，給出三角形的行數(shù)。下面的N行給出數(shù)字三角形。數(shù)字三角形上的數(shù)的范圍都在0和100之間。輸出輸出最大的和。樣例輸入5738810274445265樣例輸出30考生答案：（此題已作答）考生得分：25是否評(píng)分：已評(píng)分評(píng)價(jià)描述：2.大盜

試題編號(hào)：試題類(lèi)型：編程題標(biāo)準(zhǔn)答案：試題難度：一般試題解析：展示地址：點(diǎn)擊瀏覽大盜阿福是一名經(jīng)驗(yàn)豐富的大盜。趁著月黑風(fēng)高，阿福打算今晚洗劫一條街上的店鋪。這條街上一共有N家店鋪，每家店中都有一些現(xiàn)金。阿福事先調(diào)查得知，只有當(dāng)他同時(shí)洗劫了兩家相鄰的店鋪時(shí)，街上的報(bào)警系統(tǒng)才會(huì)啟動(dòng)，然后警察就會(huì)蜂擁而至。作為一向謹(jǐn)慎作案的大盜，阿福不愿意冒著被警察追捕的風(fēng)險(xiǎn)行竊。他想知道，在不驚動(dòng)警察的情況下，他今晚最多可以得到多少現(xiàn)金？時(shí)間限制：1000內(nèi)存限制：65536輸入輸入的第一行是一個(gè)整數(shù)T(T<=50)，表示一共有T組數(shù)據(jù)。接下來(lái)的每組數(shù)據(jù)，第一行是一個(gè)整數(shù)N(1<=N<=100,000)，表示一共有N家店鋪。第二行是N個(gè)被空格分開(kāi)的正整數(shù)，表示每一家店鋪中的現(xiàn)金數(shù)量。每家店鋪中的現(xiàn)金數(shù)量均不超過(guò)1000。輸出對(duì)于每組數(shù)據(jù)，輸出一行。該行包含一個(gè)整數(shù)，表示阿福在不驚動(dòng)警察的情況下可以得到的現(xiàn)金數(shù)量。樣例輸入231824107614樣例輸出824提示對(duì)于第一組樣例，阿福選擇第2家店鋪行竊，獲得的現(xiàn)金數(shù)量為8。對(duì)于第二組樣例，阿福選擇第1和4家店鋪行竊，獲得的現(xiàn)金數(shù)量為10+14=24。考生答案：（此題已作答）考生得分：25是否評(píng)分：已評(píng)分評(píng)價(jià)描述：3.最大子矩陣

試題編號(hào)：試題類(lèi)型：編程題標(biāo)準(zhǔn)答案：試題難度：一般試題解析：展示地址：點(diǎn)擊瀏覽最大子矩陣已知矩陣的大小定義為矩陣中所有元素的和。給定一個(gè)矩陣，你的任務(wù)是找到最大的非空(大小至少是1*1)子矩陣。比如，如下4*4的矩陣0-2-7092-62-41-41-180-2的最大子矩陣是92-41-18這個(gè)子矩陣的大小是15。時(shí)間限制：1000內(nèi)存限制：65536輸入輸入是一個(gè)N*N的矩陣。輸入的第一行給出N(0<N<=100)。再后面的若干行中，依次（首先從左到右給出第一行的N個(gè)整數(shù)，再?gòu)淖蟮接医o出第二行的N個(gè)整數(shù)……）給出矩陣中的N2個(gè)整數(shù)，整數(shù)之間由空白字符分隔（空格或者空行）。已知矩陣中整數(shù)的范圍都在[-127,127]。輸出輸出最大子矩陣的大小。樣例輸入40-2-7092-62-41-41-180-2樣例輸出15考生答案：（此題已作答）考生得分：25是否評(píng)分：已評(píng)分評(píng)價(jià)描述：4.小球放盒子

試題編號(hào)：試題類(lèi)型：編程題標(biāo)準(zhǔn)答案：試題難度：一般試題解析：展示地址：點(diǎn)擊瀏覽小球放盒子有N個(gè)相同的球，M個(gè)不同的盒子，每個(gè)盒子最多放K個(gè)球

請(qǐng)計(jì)算將這N個(gè)球全部放入盒子中的方案數(shù)模1000007后的結(jié)果時(shí)間限制：10000內(nèi)存限制：131072輸入三個(gè)正整數(shù)，依次為N，M，K輸出輸出方案數(shù)模1000007后的結(jié)果樣例輸入423樣例輸出3提示總共有3種方案，依