1999年第11届国际信息学奥赛试题

《1999年第11届国际信息学奥赛试题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1999年第11届国际信息学奥赛试题解析（精选）第一题花店橱窗布置问题LITTLESHOPOFFLOWERSDay1.Sourcefileflower.*.Maximumrunningtime:2s.PROBLEM:Youwanttoarrangethewindowofyourflowershopinamostpleasantway.YouhaveFbunchesofflowers,eachbeingofadifferentkind,andatleastasmanyvasesorderedinarow.Thevasesareglu

2、edontotheshelfandarenumberedconsecutively1throughV,whereVisthenumberofvases,fromlefttorightsothatthevase1istheleftmost,andthevaseVistherightmostvase.Thebunchesaremoveableandareuniquelyidentifiedbyintegersbetween1andF.Theseid-numbershaveasignificance:Theydeterminethere

3、quiredorderofappearanceoftheflowerbunchesintherowofvasessothatthebunchimustbeinavasetotheleftofthevasecontainingbunchjwheneveri

4、tbeputintothevaseskeepingtheirid-numbersinorder.Thebunchofazaleasmustbeinavasetotheleftofbegonias,andthebunchofbegoniasmustbeinavasetotheleftofcarnations.Iftherearemorevasesthanbunchesofflowersthentheexcesswillbeleftempty.Avasecanholdonlyonebunchofflowers.Eachvasehasa

5、distinctcharacteristic(justlikeflowersdo).Hence,puttingabunchofflowersinavaseresultsinacertainaestheticvalue,expressedbyaninteger.Theaestheticvaluesarepresentedinatableasshownbelow.Leavingavaseemptyhasanaestheticvalueof0.VASES5412345Bunches1(azaleas)723－5－24162(begoni

6、as)521－410233(carnations)－215－4－2020Accordingtothetable,azaleas,forexample,wouldlookgreatinvase2,buttheywouldlookawfulinvase4.Toachievethemostpleasanteffectyouhavetomaximizethesumofaestheticvaluesforthearrangementwhilekeepingtherequiredorderingoftheflowers.Ifmorethano

7、nearrangementhasthemaximalsumvalue,anyoneofthemwillbeacceptable.Youhavetoproduceexactlyonearrangement.ASSUMPTIONS:●1≤F≤100whereFisthenumberofthebunchesofflowers.Thebunchesarenumbered1throughF.●F≤V≤100whereVisthenumberofvases.●－50≤Aij≤50whereAij,istheaestheticvalueobta

8、inedbyputtingtheflowerhunchIintothevasej.INPUT:Theinputisatextfilenamedflower.inp.●Thefirstlinecontainstwonumbers:F,V.●Thefo