|
选课 score.pas
学校实行学分制。每门的必修课都有固定的学分，同时还必须获得相应的选修课程学分。学校开设了N（N<300）门的选修课程，每个学生可选课程的数量M是给定的。学生选修了这M门课并考核通过就能获得相应的学分。在选修课程中，有些课程可以直接选修，有些课程需要一定的基础知识，必须在选了其它的一些课程的基础上才能选修。例如《Frontpage》必须在选修了《Windows操作基础》之后才能选修。我们称《Windows操作基础》是《Frontpage》的先修课。每门课的直接先修课最多只有一门。两门课也可能存在相同的先修课。每门课都有一个课号，依次为1，2，3，…。例如: 课号 先修课号 学分 1 无 1 2 1 1 3 2 3 4 无 3 5 2 4 表中1是2的先修课，2是3、4的先修课。如果要选3，那么1和2都一定已被选修过。 你的任务是为自己确定一个选课方案，使得你能得到的学分最多，并且必须满足先修课优先的原则。假定课程之间不存在时间上的冲突。 程序名：score 输入格式： 输入文件的第一行包括两个整数N、M（中间用一个空格隔开），其中1≤N≤300,1≤M≤N。 以下N行每行代表一门课。课号依次为1，2，…，N。每行有两个数（用一个空格隔开），第一个数为这门课先修课的课号（若不存在先修课则该项为0），第二个数为这门课的学分。学分是不超过10的正整数。 输出格式： 输出文件只有一个数：实际所选课程的学分总数。 输入样例： 7 4 2 2 0 1 0 4 2 1 7 1 7 6 2 2 输出样例： 13 【解析】 首先可以从题目中看出这是一类树形动态规划题。为了方便储存，可以将多叉树转化为二叉树，常用的表示方法是左孩子右兄弟表示法。设f[i,j]表示以i为节点选j门课所获得的最大学分，则f[I,J]:=max(f[left[i],k]+f[right[i],j-k]);0<=k<=j。f[right[i].j-k]表示右孩子只能选j-k门课。以-oo表示空节点，0表示根节点，1~n是n门可选课的节点。在竞赛中如何规划用递归思想来实现动态规划很重要。 program score; const filename='score'; type xx=record left,right,num:longint; end; var f:array[0..300,0..300] of longint; son:array[0..300] of longint; tree:array[0..300] of xx; n,m:longint; function dfs(v,p:longint):longint; var i,t,max:longint; begin if f[v,p]>=0 then exit(f[v,p]); //若该值已求出，或者改位置为哨兵位置则跳出 if (v=0) or (p=0) then begin f[v,p]:=0; exit(0); end; max:=dfs(tree[v].right,p); for i:=0 to p-1 do //在进入“部分选择来自此节点的儿子节点，部分选择来自此节点和平行的兄弟节点”状态 begin t:=dfs(tree[v].left,i)+dfs(tree[v].right,p-i-1)+tree[v].num; if t>max then max:=t; end; f[v,p]:=max; exit(f[v,p]); end; procedure init; var i,x:longint; begin readln(n,m); fillchar(son,sizeof(son),0); fillchar(f,sizeof(f),$8F); for i:=1 to n do //左孩子右兄弟表示法 begin readln(x,tree[i].num); if son[x]=0 then tree[x].left:=i else tree[son[x]].right:=i; son[x]:=i; end; end; begin assign(input,filename+'.in'); reset(input); assign(output,filename+'.out'); rewrite(output); init; writeln(dfs(tree[0].left,m)); close(input); close(output); end. 问题描述
几乎整个Byteland王国都被森林和河流所覆盖。小点的河汇聚到一起，形成了稍大点的河。就这样，所有的河水都汇聚并流进了一条大河，最后这条大河流进了大海。这条大河的入海口处有一个村庄——名叫Bytetown。 在Byteland国，有n个伐木的村庄，这些村庄都座落在河边。目前在Bytetown，有一个巨大的伐木场，它处理着全国砍下的所有木料。 木料被砍下后，顺着河流而被运到Bytetown的伐木场。Byteland的国王决定，为了减少运输木料的费用，再额外地建造k个伐木场。这k个伐木场将被建在其他村庄里。这些伐木场建造后，木料就不用都被送到Bytetown了，它们可以在 运输过程中第一个碰到的新伐木场被处理。 显然，如果伐木场座落的那个村子就不用再付运送木料的费用了。它们可以直接被本村的伐木场处理。 注意：所有的河流都不会分叉，也就是说，每一个村子，顺流而下都只有一条路——到bytetown。 国王的大臣计算出了每个村子每年要产多少木料，你的任务是决定在哪些村子建设伐木场能获得最小的运费。其中运费的计算方法为：每一块木料每千米1分钱。 编一个程序：
1．从文件读入 村子的个数，另外要建设的伐木场的数目，每年每个村子产的木料的块数以及河流的描述。 2．计算最小的运费并输出。 输入输出 第一行 包括两个数 n（2<=n<=100），k（1<=k<=50,且 k<=n）。n为村庄数，k为要建的伐木场的数目。除了bytetown外，每个村子依次被命名为1，2，3……n，bytetown被命名为0。 接下来n行，每行包涵3个整数 wi——每年i村子产的木料的块数0020（0<=wi<=10000） vi——离i村子下游最近的村子（或bytetown）（0<=vi<=n） di——vi到i的距离(km)。（1<=di<=10000） 输出包含一行，即最小的运费。
保证每年所有的木料流到bytetown的运费不超过2000，000，000分
50％的数据中 n不超过20。 【解析】 此题很明显的是一个树形动态规划题。 定义F[I,J,Fa]代表以I节点为根的子树，新增J个木材处理厂，离它最近的木材处理厂是Fa，，有如下方程： F[I,J,Fa]:=Min{F[Left[I],K,Fa]+F[Right[I],J-K,Fa]+Cost[I]*(Dis[I]-Dis[Fa])，F[Left[I],K,I]+F[Right[I],J-K-1,Fa]} 仍然用左孩子右兄弟来实现多叉转二叉。需要提前预处理出来一点到其余各点间的距离。 program river; const filename='river'; type xx=record l,r,w:longint; end; node=record //记录以i为根的所有结点信息 num:longint; v:array[1..100] of longint; end; var a:array[-1..100] of node; tree:array[-1..100] of xx; flag:array[-1..100,-1..100,-1..100] of boolean; son,dis:array[-1..100] of longint; f:array[-1..100,-1..100,-1..100] of longint; //f[]表示以s为根，建立p个伐木场，且离s最近的点为k时的最优值 map:array[-1..100,-1..100] of longint; n,m:longint; procedure init; var i,v:longint; begin readln(n,m); fillchar(son,sizeof(son),$FF); fillchar(tree,sizeof(tree),$FF); fillchar(flag,sizeof(flag),false); fillchar(f,sizeof(f),$7F); fillchar(a,sizeof(a),0); for i:=1 to n do //左孩子右兄弟 begin readln(tree[i].w,v,map[i,v]); if son[v]<0 then tree[v].l:=i else tree[son[v]].r:=i; son[v]:=i; map[v,i]:=map[i,v]; inc(a[v].num); a[v].v[a[v].num]:=i; end; end; procedure pretreatment(x,s:longint); //预处理一点到其余各点间的距离 var i:longint; begin dis[x]:=s; for i:=1 to a[x].num do //所有与x相连的结点 pretreatment(a[x].v[i],dis[x]+map[a[x].v[i],x]); end; function min(a,b:longint):longint; begin if a<b then exit(a) else exit(b); end; procedure dfs(s,k,p:longint); //以s为根，建立p个伐木场，且离s最近的点为k时的最优值 var i,j:longint; begin if s<0 then begin f[s,k,p]:=0; exit; end; if flag[s,k,p] then exit; //不重复搜索 flag[s,k,p]:=true; //记忆化 for i:=0 to p do begin dfs(tree[s].l,k,i); dfs(tree[s].r,k,p-i); f[s,k,p]:=min(f[s,k,p],f[tree[s].l,k,i]+f[tree[s].r,k,p-i]+tree[s].w*abs((dis[k]-dis[s]))); //s处不设置伐木场的状态 if p-i-1>=0 then begin dfs(tree[s].l,s,i); dfs(tree[s].r,k,p-i-1); f[s,k,p]:=min(f[s,k,p],f[tree[s].l,s,i]+f[tree[s].r,k,p-i-1]); //s处设置伐木场的状态 end; end; end; begin assign(input,filename+'.in'); reset(input); assign(output,filename+'.out'); rewrite(output); init; pretreatment(0,0); dfs(0,0,m); writeln(f[0,0,m]); close(input); close(output); end. 没有上司的晚会 【问题描述】 有个公司要举行一场晚会。为了让到会的每个人不受他的直接上司约束而能玩得开心，公司领导决定：如果邀请了某个人，那么一定不会再邀请他的直接的上司，但该人的上司的上司，上司的上司的上司……都可以邀请。已知每个人最多有唯一的一个上司。 已知公司的每个人参加晚会都能为晚会增添一些气氛，求一个邀请方案，使气氛值的和最大。 【输入：】 第1行一个整数N（1<=N<=6000）表示公司的人数。 接下来N行每行一个整数。第i行的书表示第i个人的气氛值x（-128<=x<=127）。 接下来每行两个整数L，K。表示第K个人是第L个人的上司。 输入以0 0结束。 【输出】： 一个数，最大的气氛值和。 【样例输入】 7 1 1 1 1 1 1 1 1 3 2 3 6 4 7 4 4 5 3 5 0 0 【样例输出】 5 【分析】 如上例，上司与小兵之间的关系构成一棵树。 5 | \ 3 4 | \ | \ 1 2 6 7 又是求最优解，并且每一个节点的取舍关乎到全局 因此，此题可用树形动态规划 我们可用f[v][0]存储不选编号为V的节点的最优解，f[v][1]存储选编号为V的节点的最优解 #include<iostream> using namespace std; int main(){ int n,qf[201],f[201][2],shs[201],xb[201][201],shu[201][201],x,s,maxc,j,k,a,b,l,i;//qf存储每个人的气氛值，shs存储每个人的上司，xb存储没个人的下属，shu存储构成的树 cin>>n; for(i=0;i<=n;i++){xb[i][0]=0;shs[i]=0;} for(i=1;i<=n;i++)cin>>qf[i];l=1;k=1; while(l!=0 || k!=0){ cin>>l>>k; shs[l]=k; xb[k][0]++; xb[k][xb[k][0]]=l; } maxc=0; for(i=1;i<=n;i++) { x=i;s=1; while(shs[x]!=0){x=shs[x];s=s+1;} shu[s][0]++; shu[s][shu[s][0]]=i; if (s>maxc)maxc=s; }//建树,maxc存储最大层数 for(i=maxc;i>=1;i--) for(j=1;j<=shu[i][0];j++) { if(xb[shu[i][j]][0]==0){ f[shu[i][j]][0]=0;f[shu[i][j]][1]=qf[shu[i][j]]; } else { f[shu[i][j]][0]=0;f[shu[i][j]][1]=qf[shu[i][j]]; for(k=1;k<=xb[shu[i][j]][0];k++){ a=f[xb[shu[i][j]][k]][0];b=f[xb[shu[i][j]][k]][1]; f[shu[i][j]][1]+=a; if(b>a)a=b; f[shu[i][j]][0]+=a; }//动态转移方程 } }s=0; for(i=1;i<=shu[1][0];i++){ a=f[shu[1][i]][0];b=f[shu[1][i]][1]; if(a<b)a=b; s=s+a; }//从顶头上司那里择优选择 cout<<s<<endl; system("pause"); return 0; } |
|
|
