2012福建省信息学奥林匹克CCF-NOIP夏令营第八天训练(附解题思路及参考程序)

(完整版)2012福建省信息学奥林匹克CCFNOIP夏令营第八天训练(附解题思路及参考程序)(完整版)2012福建省信息学奥林匹克CCFNOIP夏令营第八天训练(附解题思路及参考程序)(完整版)2012福建省信息学奥林匹克CCFNOIP夏令营第八天训练(附解题思路及参考程序)2012福建省信息学奥林匹克CCFNOIP夏令营第八天训练（附解题思路及参考程序）问题名称文件名输入文件输出文件时限分值最长上升子序列sequencesequence.insequence。out1s100没有上司的舞会anivaniv.inaniv。out1s100贝茜的晨练计划cowruncowrun.incowrun.out1s100内存限制均为256M

最长上升子序列（sequence）【问题描述】非常经典的问题，拿来给大家练手了.序列{1,2，.。。,n}的一个子序列是指序列｛i1,i2，……，ik}，其中1〈=i1<i2<……〈ik<=n，序列｛a1，a2,……,an}的一个子序列是指序列{ai1，ai2,……,aik｝,其中｛i1,i2,……,ik}是{1，2，……,n｝的一个子序列。同时，称k为此子序列的长度.如果｛ai1，ai2,……，aik｝满足ai1≤ai2≤……≤aik,则称之为上升子序列。如果不等号都是严格成立的,则称之为严格上升子序列。同理，如果前面不等关系全部取相反方向,则称之为下降子序列和严格下降子序列.长度最长的上升子序列称为最长上升子序列。本问题对于给定的整数序列，请求出其最长上升子序列的长度.【输入文件】第一行给出一个数字N,N〈=5000，表示给定数列的长度。第二行有N个整数，表示数列中的元素【输出文件】输出K的极大值，即最长上升子序列的长度【样例输入】593627【样例输出】3【样例解释】最长上升子序列为3,6，7【说明】此题非常基础,希望每个人都能拿到此题的全部分数

舞会（aniv）【问题描述】某大学有N个职员，编号为1～N。他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数Ri，但是呢，如果某个职员的上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了.所以,请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。【输入文件】第一行一个整数N。(1<=N<=6000）接下来N行,第i+1行表示i号职员的快乐指数Ri。(-128<=Ri<=127）接下来N-1行，每行输入一对整数L,K。表示K是L的直接上司。最后一行输入00【输出文件】输出最大的快乐指数。【样例输入】7111111113236474453500【样例输出】5

贝茜的晨练计划(cowrun)【问题描述】奶牛们打算通过锻炼来培养自己的运动细胞,作为其中的一员,贝茜选择的运动方式是每天进行N（1<=N〈=10，000）分钟的晨跑。在每分钟的开始，贝茜会选择下一分钟是用来跑步还是休息。贝茜的体力限制了她跑步的距离.更具体地，如果贝茜选择在第i分钟内跑步，她可以在这一分钟内跑D_i（1<=D_i〈=1，000）米，并且她的疲劳度会增加1.不过,无论何时贝茜的疲劳度都不能超过M（1〈=M〈=500)。如果贝茜选择休息,那么她的疲劳度就会每分钟减少1,但她必须休息到疲劳度恢复到0为止。在疲劳度为0时休息的话，疲劳度不会再变动。晨跑开始时，贝茜的疲劳度为0。还有，在N分钟的锻炼结束时,贝茜的疲劳度也必须恢复到0,否则她将没有足够的精力来对付这一整天中剩下的事情。请你计算一下，贝茜最多能跑多少米.【输入文件】第1行:2个用空格隔开的整数：N和M第2..N+1行：第i+1为1个整数：D_i【输出文件】输出1个整数，表示在满足所有限制条件的情况下,贝茜能跑的最大距离【样例输入】52534210【样例输出】9【样例说明】贝茜在第1分钟内选择跑步（跑了5米），在第2分钟内休息,在第3分钟内跑步（跑了4米）,剩余的时间都用来休息.因为在晨跑结束时贝茜的疲劳度必须为0，所以她不能在第5分钟内选择跑步

今天的关键在于认真检查程序，不要会做却丢分.最长上升子序列：经典水题题目大意:求一个数列的最长上升子序列解题思路:F［i］表示以第i个元素结尾的最长上升子序列F［i]=max（f［j])+1j<i且a[j］<a[i］此题有许多种加强和变形的版本，有兴趣的可以去研究一下。参考程序：＃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;}

没有上司的舞会：树形动规题目大意：在一个树结构的图中，每个节点都有一个快乐值,要求在这其中选择一些节点并累加快乐值，但不能同时选择相连的父子节点.求最大的快乐值。解题思路：典型的树形动规f[i][0]表示不选节点i的情况下，以i为根节点的子树的最大快乐值f[i］［1］表示选取节点i的情况的最大快乐值f[i]［0]+=MAX（f［j][0］，f［j］[1]）f[i]［1]+=f[j]［0]节点j为节点i的子节点,若选取节点i，则其子节点只能不选。参考程序：＃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；｝

贝茜的晨练计划:常见动规题目大意：有N分钟的时间,第i分钟可以选择跑Di米并增加1疲惫度，或休息并减少1疲惫度，疲惫度不能超过M，一旦开始休息必须休息至疲惫度为0。N分钟结束后贝茜的疲惫度必须为0。求贝茜能跑的最大距离。解题思路：f［i］[j］表示N分钟后贝茜的疲惫值为j时已跑的最大距离。最形象的状态转移方式：对于已知的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时特判参考程序：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