2012福建省信息學(xué)奧林匹克CCF-NOIP夏令營(yíng)第八天訓(xùn)練(附解題思路及參考程序)

(完整版)2012福建省信息學(xué)奧林匹克CCFNOIP夏令營(yíng)第八天訓(xùn)練(附解題思路及參考程序)(完整版)2012福建省信息學(xué)奧林匹克CCFNOIP夏令營(yíng)第八天訓(xùn)練(附解題思路及參考程序)(完整版)2012福建省信息學(xué)奧林匹克CCFNOIP夏令營(yíng)第八天訓(xùn)練(附解題思路及參考程序)2012福建省信息學(xué)奧林匹克CCFNOIP夏令營(yíng)第八天訓(xùn)練（附解題思路及參考程序）問題名稱文件名輸入文件輸出文件時(shí)限分值最長(zhǎng)上升子序列sequencesequence.insequence。out1s100沒有上司的舞會(huì)anivaniv.inaniv。out1s100貝茜的晨練計(jì)劃cowruncowrun.incowrun.out1s100內(nèi)存限制均為256M

最長(zhǎng)上升子序列（sequence）【問題描述】非常經(jīng)典的問題，拿來給大家練手了.序列{1,2，.。。,n}的一個(gè)子序列是指序列｛i1,i2，……，ik}，其中1〈=i1<i2<……〈ik<=n，序列｛a1，a2,……,an}的一個(gè)子序列是指序列{ai1，ai2,……,aik｝,其中｛i1,i2,……,ik}是{1，2，……,n｝的一個(gè)子序列。同時(shí)，稱k為此子序列的長(zhǎng)度.如果｛ai1，ai2,……，aik｝滿足ai1≤ai2≤……≤aik,則稱之為上升子序列。如果不等號(hào)都是嚴(yán)格成立的,則稱之為嚴(yán)格上升子序列。同理，如果前面不等關(guān)系全部取相反方向,則稱之為下降子序列和嚴(yán)格下降子序列.長(zhǎng)度最長(zhǎng)的上升子序列稱為最長(zhǎng)上升子序列。本問題對(duì)于給定的整數(shù)序列，請(qǐng)求出其最長(zhǎng)上升子序列的長(zhǎng)度.【輸入文件】第一行給出一個(gè)數(shù)字N,N〈=5000，表示給定數(shù)列的長(zhǎng)度。第二行有N個(gè)整數(shù)，表示數(shù)列中的元素【輸出文件】輸出K的極大值，即最長(zhǎng)上升子序列的長(zhǎng)度【樣例輸入】593627【樣例輸出】3【樣例解釋】最長(zhǎng)上升子序列為3,6，7【說明】此題非?；A(chǔ),希望每個(gè)人都能拿到此題的全部分?jǐn)?shù)

舞會(huì)（aniv）【問題描述】某大學(xué)有N個(gè)職員，編號(hào)為1～N。他們之間有從屬關(guān)系，也就是說他們的關(guān)系就像一棵以校長(zhǎng)為根的樹，父結(jié)點(diǎn)就是子結(jié)點(diǎn)的直接上司。現(xiàn)在有個(gè)周年慶宴會(huì)，宴會(huì)每邀請(qǐng)來一個(gè)職員都會(huì)增加一定的快樂指數(shù)Ri，但是呢，如果某個(gè)職員的上司來參加舞會(huì)了，那么這個(gè)職員就無論如何也不肯來參加舞會(huì)了.所以,請(qǐng)你編程計(jì)算，邀請(qǐng)哪些職員可以使快樂指數(shù)最大，求最大的快樂指數(shù)?！据斎胛募康谝恍幸粋€(gè)整數(shù)N。(1<=N<=6000）接下來N行,第i+1行表示i號(hào)職員的快樂指數(shù)Ri。(-128<=Ri<=127）接下來N-1行，每行輸入一對(duì)整數(shù)L,K。表示K是L的直接上司。最后一行輸入00【輸出文件】輸出最大的快樂指數(shù)?！緲永斎搿?111111113236474453500【樣例輸出】5

貝茜的晨練計(jì)劃(cowrun)【問題描述】奶牛們打算通過鍛煉來培養(yǎng)自己的運(yùn)動(dòng)細(xì)胞,作為其中的一員,貝茜選擇的運(yùn)動(dòng)方式是每天進(jìn)行N（1<=N〈=10，000）分鐘的晨跑。在每分鐘的開始，貝茜會(huì)選擇下一分鐘是用來跑步還是休息。貝茜的體力限制了她跑步的距離.更具體地，如果貝茜選擇在第i分鐘內(nèi)跑步，她可以在這一分鐘內(nèi)跑D_i（1<=D_i〈=1，000）米，并且她的疲勞度會(huì)增加1.不過,無論何時(shí)貝茜的疲勞度都不能超過M（1〈=M〈=500)。如果貝茜選擇休息,那么她的疲勞度就會(huì)每分鐘減少1,但她必須休息到疲勞度恢復(fù)到0為止。在疲勞度為0時(shí)休息的話，疲勞度不會(huì)再變動(dòng)。晨跑開始時(shí)，貝茜的疲勞度為0。還有，在N分鐘的鍛煉結(jié)束時(shí),貝茜的疲勞度也必須恢復(fù)到0,否則她將沒有足夠的精力來對(duì)付這一整天中剩下的事情。請(qǐng)你計(jì)算一下，貝茜最多能跑多少米.【輸入文件】第1行:2個(gè)用空格隔開的整數(shù)：N和M第2..N+1行：第i+1為1個(gè)整數(shù)：D_i【輸出文件】輸出1個(gè)整數(shù)，表示在滿足所有限制條件的情況下,貝茜能跑的最大距離【樣例輸入】52534210【樣例輸出】9【樣例說明】貝茜在第1分鐘內(nèi)選擇跑步（跑了5米），在第2分鐘內(nèi)休息,在第3分鐘內(nèi)跑步（跑了4米）,剩余的時(shí)間都用來休息.因?yàn)樵诔颗芙Y(jié)束時(shí)貝茜的疲勞度必須為0，所以她不能在第5分鐘內(nèi)選擇跑步

今天的關(guān)鍵在于認(rèn)真檢查程序，不要會(huì)做卻丟分.最長(zhǎng)上升子序列：經(jīng)典水題題目大意:求一個(gè)數(shù)列的最長(zhǎng)上升子序列解題思路:F［i］表示以第i個(gè)元素結(jié)尾的最長(zhǎng)上升子序列F［i]=max（f［j])+1j<i且a[j］<a[i］此題有許多種加強(qiáng)和變形的版本，有興趣的可以去研究一下。參考程序：＃include<iostream〉#include<cstring>#include〈cstdio>#include〈cstdlib>#include〈cmath>usingnamespacestd;＃defineFOR（i，a,b)for(inti=a；i〈=b；i++）#defineMST（a，b)memset(a，b,sizeof（a))#defineMAXN5050intn，a［MAXN］,f［MAXN];intmain（）｛freopen("sequence.in”,”r"，stdin);freopen（"sequence.out"，"w"，stdout);scanf("%d”，&n）;FOR（i，1,n)scanf(”％d”，＆a[i])；MST(f,0）；f[1]=1;FOR（i,2,n){f[i]=1;FOR（j,1,i-1）if（(a[j]<=a［i]）＆&(f[j]+1〉f［i])）f［i］=f[j］+1；｝intans=0；FOR(i,1，n)if(f[i]〉ans)ans=f［i］；cout〈<ans;}

沒有上司的舞會(huì)：樹形動(dòng)規(guī)題目大意：在一個(gè)樹結(jié)構(gòu)的圖中，每個(gè)節(jié)點(diǎn)都有一個(gè)快樂值,要求在這其中選擇一些節(jié)點(diǎn)并累加快樂值，但不能同時(shí)選擇相連的父子節(jié)點(diǎn).求最大的快樂值。解題思路：典型的樹形動(dòng)規(guī)f[i][0]表示不選節(jié)點(diǎn)i的情況下，以i為根節(jié)點(diǎn)的子樹的最大快樂值f[i］［1］表示選取節(jié)點(diǎn)i的情況的最大快樂值f[i]［0]+=MAX（f［j][0］，f［j］[1]）f[i]［1]+=f[j]［0]節(jié)點(diǎn)j為節(jié)點(diǎn)i的子節(jié)點(diǎn),若選取節(jié)點(diǎn)i，則其子節(jié)點(diǎn)只能不選。參考程序：＃include<cstdio>＃include〈cstring>＃include<algorithm>usingnamespacestd；structEDGE{intv,next；}edge[6010]；intc[6005］；boolin[6005];intf[6005]［2];intcnt；inthead[6010];voidaddedge（intu，intv）｛edge［cnt］。v=v；edge［cnt］.next=head［u］;head［u］=cnt++；｝voiddp(intu）｛f[u]［1］=c［u］;f［u］[0］=0;for(intp=head［u]；p！=—1;p=edge［p］。next）{intv=edge[p］。v;dp(v);f［u］[1］=max（f［u][1］,f[v][0］+f［u］［1］）；f［u］［0]=f［u][0]+max（f[v][1]，f［v][0]）；｝}intmain(){freopen（”aniv。in”，"r"，stdin）；freopen(”aniv.out”,"w”,stdout）；intn;scanf(”％d",&n)；for（inti=1；i<=n;i++）scanf（"％d",&c[i］）;cnt=0;memset（in,false，sizeof（in））;memset（head,—1,sizeof（head))；intx,y;for（inti=1;i〈n；i++）{scanf（”%d％d"，&x,&y）；in[x]=true;addedge(y,x）；｝scanf（"%d%d",＆x，&y)；memset(f，0，sizeof(f）)；for(inti=1;i〈=n;i++)if（!in［i])｛dp（i)；printf(”%d”，f[i]［0]>f[i]［1]?f[i][0］:f［i]［1］）；break;｝return0；｝

貝茜的晨練計(jì)劃:常見動(dòng)規(guī)題目大意：有N分鐘的時(shí)間,第i分鐘可以選擇跑Di米并增加1疲憊度，或休息并減少1疲憊度，疲憊度不能超過M，一旦開始休息必須休息至疲憊度為0。N分鐘結(jié)束后貝茜的疲憊度必須為0。求貝茜能跑的最大距離。解題思路：f［i］[j］表示N分鐘后貝茜的疲憊值為j時(shí)已跑的最大距離。最形象的狀態(tài)轉(zhuǎn)移方式：對(duì)于已知的f[i]［j］若接下來1分鐘跑步f[i+1]［j+1]=MAX(f[i+1][j+1],f［i][j]+D[i+1］）若下一分鐘開始休息f［i+j][0]=MAX(f［i+j]［0］，f［i]［j])//注意j=0時(shí)特判參考程序：varn，m，i，j：longint；f：array［0.。10001，0..501]oflongint;a，s：array［0.。10001]oflongint；functionmax（a，b:longint)：longint;beginifa>bthenexit（a）elseexit(b）；end；beginassign(input，'cowrun.in')；reset（input）;assign（output,’cowrun。out’)；rewrite(output）；readln(n,m）;fillchar(f，sizeof(f），0)；fori：=1tondobeginreadln（a［i]）；s［i］：=s[i—1］+a[i］;end；fori:=1tondobeginforj：=0tom+i—max（m,i）dobeginifj=0thenf［i,j]：=m