选课 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;
}