作业帮 > 综合 > 作业

聚会的快乐(party.exe)

来源:学生作业帮 编辑:拍题作业网作业帮 分类:综合作业 时间:2024/05/01 22:20:12
聚会的快乐(party.exe)
【问题描述】
你要组织一个由你公司的人参加的聚会.尽可能多地找些有趣的热闹.但是劝你不要同时邀请某个人和他的上司,因为这可能带来争吵.给定N个人(姓名,他幽默的系数,以及他上司的名字),编程找到能使幽默系数和最大的若干个人.
【输入】
第一行一个整数N(Nb then exit(a) else exit(b);
end;
procedure treedp(t:longint);
var i:longint;
begin
for i:=1 to son[t,0] do
treedp(son[t,i]);
for i:=1 to son[t,0] do
begin
f[t,0]:=max(f[son[t,i],0],f[son[t,i],1])+f[t,0];
f[t,1]:=f[son[t,i],0]+f[t,1];
end;
end;
begin
assign(input,'party.in');reset(input);
assign(output,'party.out');rewrite(output);
readln(n);
for l:=1 to n do
begin
readln(s);
t:=pos(' ',s);
s1:=copy(s,1,t-1);
u:=0;
for i:=1 to k do
if s1=g[i] then begin u:=i;break;end;
if u=0 then begin inc(k);g[k]:=s1;u:=k;end;
delete(s,1,t);
t:=pos(' ',s);
s1:=copy(s,1,t-1);
val(s1,a[u],code);
delete(s,1,t);
u1:=0;
for i:=1 to k do
if s=g[i] then begin u1:=i;break;end;
if u1=0 then begin inc(k);g[k]:=s;u1:=k;end;
inc(son[u1,0]);
son[u1,son[u1,0]]:=u;
fa[u]:=u1;
end;
for i:=0 to k do begin f[i,1]:=a[i];f[i,0]:=0;end;
for i:=1 to k do
if fa[i]=0 then
begin
inc(son[0,0]);
son[0,son[0,0]]:=i;
end;
treedp(0);
writeln(max(f[0,0],f[0,1]));
close(input);close(output);
end.
错了一个点,求找错误.
题解如下
【问题分析】
用动态规划求解.首先,很显然公司的人员关系构成了一棵树.设f[a]为a参加会议的情况下,以他为根的子树取得的最大幽默值;g[a]为a不参加会议的情况下,以他为根的子树取得的最大幽默值.那么,状态转移方程就是:
\x05f[a]=g[b1]+g[b2]+…+g[bk]+w[a]
\x05g[a]=max(f[b1],g[b1])+max(f[b2],g[b2])+…+max(f[bk],g[bk])
\x05其中b1,b2,…,bk为a的子结点.
\x05最后的答案就是max(f[root],g[root]),root是树根.
抱歉,错误数据发不上来,只错了一个点.要错的哪一个点数据的请留邮箱.回答出来,我还会追加分数
我认为你的程序是对的 可能是题目或数据不太对
你给我的数据中:
14行:FD 50 AEMHOCH
45行:FD 4 FKYOIE
这是什么情况?一个人有两个上司和两个幽默度?
可能是这数据出了点小问题吧
(ps:这题树根上的上司是没有幽默度的?)