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

2012福建省信息学奥林匹克CCF NOIP 夏令营第八天训练（附解题思路及参考程序）内存限制均为256M问题名称 文件名 输入文件 输出文件 时限 分值 最长上升子序列sequence sequence.in sequence.out 1s 100 没有上司的舞会aniv aniv.in aniv.out 1s 100 贝茜的晨练计划cowruncowrun.incowrun.out1s100最长上升子序列(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的极大值，即最长上升子序列的长度【样例输入】59 3 6 2 7【样例输出】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的直接上司。

最后一行输入0 0【输出文件】输出最大的快乐指数。

【样例输入】711111111 32 36 47 44 53 50 0【样例输出】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个整数，表示在满足所有限制条件的情况下，贝茜能跑的最大距离【样例输入】5 2534210【样例输出】9【样例说明】贝茜在第1分钟内选择跑步（跑了5米），在第2分钟内休息，在第3分钟内跑步（跑了4米），剩余的时间都用来休息。

因为在晨跑结束时贝茜的疲劳度必须为0，所以她不能在第5分钟内选择跑步今天的关键在于认真检查程序，不要会做却丢分。

最长上升子序列：经典水题题目大意：求一个数列的最长上升子序列解题思路：F[i]表示以第i个元素结尾的最长上升子序列F[i]=max(f[j])+1 j<i且a[j]<a[i]此题有许多种加强和变形的版本，有兴趣的可以去研究一下。

参考程序：#include <iostream>#include <cstring>#include <cstdio>#include <cstdlib>#include <cmath>using namespace std;#define FOR(i,a,b) for(int i=a;i<=b;i++)#define MST(a,b) memset(a,b,sizeof(a))#define MAXN 5050int n,a[MAXN],f[MAXN];int main(){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;}int ans=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>using namespace std;struct EDGE{int v,next;}edge[6010];int c[6005];bool in[6005];int f[6005][2];int cnt;int head[6010];void addedge(int u,int v){edge[cnt].v=v;edge[cnt].next=head[u];head[u]=cnt++;}void dp(int u){f[u][1]=c[u];f[u][0]=0;for(int p=head[u];p!=-1;p=edge[p].next){int v=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]);}}int main(){freopen("aniv.in","r",stdin);freopen("aniv.out","w",stdout);int n;scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&c[i]);cnt=0;memset(in,false,sizeof(in));memset(head,-1,sizeof(head));int x,y;for(int i=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(int i=1;i<=n;i++)if(!in[i]){dp(i);printf("%d",f[i][0]>f[i][1]?f[i][0]:f[i][1]);break;}return 0;}贝茜的晨练计划：常见动规题目大意：有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]of longint;a,s:array[0..10001]of longint;function max(a,b:longint):longint;beginif a>b then exit(a)else exit(b);end;beginassign(input,'cowrun.in');reset(input);assign(output,'cowrun.out');rewrite(output);readln(n,m);fillchar(f,sizeof(f),0);for i:=1 to n do beginreadln(a[i]);s[i]:=s[i-1]+a[i];end;for i:=1 to n do beginfor j:=0 to m+i-max(m,i) dobeginif j=0 then f[i,j]:=max(f[i-1,0],f[i-1,1])else if j=m then f[i,j]:=f[i-m,0]+s[i]-s[i-m]else f[i,j]:=max(f[i-j,0]+s[i]-s[i-j],f[i-1,j+1]);end;end;writeln(f[n,0]); close(input);close(output);end.。