【正文】 。 f[2,x]:=f[2,x]+c[x]。 end。Beginreadln(n,m)。for i:=1 to n do readln(c[i])。for i:=1 to m do begin readln(a,b)。 p[a,0]:=p[a,0]+1。p[a,p[a,0]]:=b。 p[b,0]:=p[b,0]+1。p[b,p[b,0]]:=a。 end。for i:=1 to n do if p[i,0]=0 then s:=s+c[i] else if not v[i] then begin make(i)。 work(i)。 s:=s+max(f[1,i],f[2,i])。 end。writeln(s)。End. 沒(méi)有上司的舞會(huì)【問(wèn)題描述】 有個(gè)公司要舉行一場(chǎng)晚會(huì)。為了讓到會(huì)的每個(gè)人不受他的直接上司約束而能玩得開(kāi)心，公司領(lǐng)導(dǎo)決定：如果邀請(qǐng)了某個(gè)人，那么一定不會(huì)再邀請(qǐng)他的直接的上司，但該人的上司的上司，上司的上司的上司……都可以邀請(qǐng)。已知每個(gè)人最多有唯一的一個(gè)上司。 已知公司的每個(gè)人參加晚會(huì)都能為晚會(huì)增添一些氣氛，求一個(gè)邀請(qǐng)方案，使氣氛值的和最大。 【輸入：】 第1行一個(gè)整數(shù)N（1=N=6000）表示公司的人數(shù)。 接下來(lái)N行每行一個(gè)整數(shù)。第i行的書(shū)表示第i個(gè)人的氣氛值x（128=x=127）。 接下來(lái)每行兩個(gè)整數(shù)L，K。表示第K個(gè)人是第L個(gè)人的上司。 輸入以0 0結(jié)束。 【輸出】： 一個(gè)數(shù)，最大的氣氛值和。 【樣例輸入】 7 1 1 1 1 1 1 1 1 3 2 3 6 4 7 4 4 5 3 5 0 0 【樣例輸出】 5【分析】如上例，上司與小兵之間的關(guān)系構(gòu)成一棵樹(shù)。5| \3 4| \ | \1 2 6 7var pres:array[1..6000]of boolean。 yes,no,now,child,pre:array[1..6000]of longint。 n,i,x,y,root:longint。function max(a,b:longint):longint。 begin if ab then max:=a else max:=b。 end。procedure dfs(v:word)。 begin while now[v]0 do begin dfs(child[now[v]])。 inc(yes[v],no[child[now[v]]])。 inc(no[v],max(yes[child[now[v]]],no[child[now[v]]]))。 now[v]:=pre[now[v]]。 end。 end。begin read(n)。 for i:=1 to n do read(yes[i])。 fillchar(pres,sizeof(pres),1)。 root:=n*(n+1) div 2。 for i:=1 to n1 do begin read(x,y)。 child[i]:=x。 pre[i]:=now[y]。 now[y]:=i。 if pres[x] then begin dec(root,x)。 pres[x]:=false。 end。 end。 dfs(root)。 writeln(max(yes[root],no[root]))。end. 選課【問(wèn)題描述】 學(xué)校實(shí)行學(xué)分制。每門(mén)的必修課都有固定的學(xué)分，同時(shí)還必須獲得相應(yīng)的選修課程學(xué)分。學(xué)校開(kāi)設(shè)了 N （N300）門(mén)的選修課程，每個(gè)學(xué)生可選課程的數(shù)量M 是給定的。學(xué)生選修了這 M 門(mén)課并考核通過(guò)就能獲得相 應(yīng)的學(xué)分。 在選修課程中，有些課程可以直接選修，有些課程需要一定的基礎(chǔ)知識(shí)，必須在選了其它的一些課程的基礎(chǔ)上才能選修。例如《FrontPage》必須在選修了《Windows 操作基礎(chǔ)》之后才能選修。我們稱《Windows 操作基礎(chǔ)》是《FrontPage》的先修課。每門(mén)課的直接先修課最多只有一門(mén)。兩門(mén)課也可能存在相同的先修課。 每門(mén)課都有一個(gè)課號(hào)，依次為 1，2，3，…。 例如: 表中 1是 2的先修課，2是 4的先修課。如果要選3，那么 1和 2都一定已被選修過(guò)。 你的任務(wù)是為自己確定一個(gè)選課方案，使得你能得到的學(xué)分最多，并且必須滿足先修課優(yōu)先的原則。假定課 程之間不存在時(shí)間上的沖突。 【輸入格式】 輸入文件的第一行包括兩個(gè)整數(shù)N、M （中間用一個(gè)空格隔開(kāi)）其中1≤N≤300,1≤M≤N。 以下N行每行代表一門(mén)課。課號(hào)依次為 1，2，…，N。每行有兩個(gè)數(shù)（用一個(gè)空格隔開(kāi)），第一個(gè)數(shù)為這門(mén)課先修課的課號(hào)（若不存在先修課則該項(xiàng)為 0），第二個(gè)數(shù)為這門(mén)課的學(xué)分。學(xué)分是不超過(guò)10的正整數(shù)。 【輸出格式】 輸出文件只有一個(gè)數(shù)：實(shí)際所選課程的學(xué)分總數(shù)。 【輸入樣例】 7 4 2 2 0 1 0 4 2 1 7 1 7 6 2 2 【輸出樣例】 13解法一：分析：首先可以從題目中看出這是一類樹(shù)形動(dòng)態(tài)規(guī)劃題。為了方便儲(chǔ)存，可以將多叉樹(shù)轉(zhuǎn)化為二叉樹(shù)，常用的表示方法是左孩子右兄弟表示法。設(shè)f[i,j]表示以i為節(jié)點(diǎn)選j門(mén)課所獲得的最大學(xué)分，則f[I,J]:=max(f[left[i],k]+f[right[i],jk])。0=k=j。f[right[i].jk]表示右孩子只能選jk門(mén)課。以oo表示空節(jié)點(diǎn)，0表示根節(jié)點(diǎn)，1~n是n門(mén)可選課的節(jié)點(diǎn)。在競(jìng)賽中如何規(guī)劃用遞歸思想來(lái)實(shí)現(xiàn)動(dòng)態(tài)規(guī)劃很重要。樹(shù)形DP。先多叉轉(zhuǎn)二叉。F[I,J]表示以I為接點(diǎn)取j門(mén)課程能得到的最大分?jǐn)?shù)。f[i,j]:=max{f[t[i].l,k]+f[t[i].r,jk1]+c[i]}program score。var n,m,dad,root:longint。 right,left,cost:array[0..1000]of longint。 f:array[0..1000,0..1000]of longint。procedure init。var i:longint。begin readln(n,m)。 for i:=1 to n do begin readln(dad,cost[i])。 right[i]:=left[dad]。 left[dad]:=i。 if dad=0 then root:=i。 end。end。function max(x,y:longint):longint。begin if xy then exit(x)。exit(y)。end。procedure treedp(k,l:longint)。var i:longint。begin if (l=0)or(k=0) then exit。 if f[k,l]0 then exit。 treedp(right[k],l)。 f[k,l]:=f[right[k],l]。 for i:=0 to l1 do begin treedp(left[k],i)。 treedp(right[k],li1)。 f[k,l]:=max(f[k,l],f[left[k],i]+f[right[k],li1]+cost[k])。 end。end。begin init。 fillchar(f,sizeof(f),0)。 treedp(root,m)。 writeln(f[root,m])。end.解法二：const filename=39。score39。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 p1 do //在進(jìn)入“部分選擇來(lái)自此節(jié)點(diǎn)的兒子節(jié)點(diǎn)，部分選擇來(lái)自此節(jié)點(diǎn)和平行的兄弟節(jié)點(diǎn)”狀態(tài) begin t:=dfs(tree[v].left,i)+dfs(tree[v].right,pi1)+tree[v].num。 if tmax 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+39。.in39。)。 reset(input)。 assign(output,filename+39。.out39。)。 rewrite(output)。 init。 writeln(dfs(tree[0].left,m))。 close(input)。 close(output)。end.解法三：【問(wèn)題分析】事先說(shuō)明題目描述有個(gè)漏洞，應(yīng)該是二個(gè)以上的課程可能有同一個(gè)先修課。換句話講，一個(gè)課程可能是多個(gè)課程的先修課，可是一個(gè)課最多只有一個(gè)先修課。這樣的描述好象和我們以前學(xué)過(guò)的一種數(shù)據(jù)結(jié)構(gòu)的描述一樣。你想對(duì)了，就是樹(shù)。因?yàn)槭墙⒃跇?shù)這種數(shù)據(jù)結(jié)構(gòu)上的最優(yōu)化問(wèn)題，我們自然想到了樹(shù)型動(dòng)態(tài)規(guī)劃。想到樹(shù)型動(dòng)態(tài)規(guī)劃，那么第一步就是想這課樹(shù)是否是二叉樹(shù)，如果不是，是否需要轉(zhuǎn)化呢？顯然這個(gè)問(wèn)題不是二叉樹(shù)，有應(yīng)為問(wèn)題是在多個(gè)課程中選M個(gè)，也就是說(shuō)是樹(shù)中一棵或多棵子樹(shù)的最優(yōu)解，這樣問(wèn)題就需要轉(zhuǎn)化成二叉樹(shù)了。注意題目中說(shuō)一個(gè)課程沒(méi)有先修課是0，也就是說(shuō)這課樹(shù)的根是0。把數(shù)據(jù)結(jié)構(gòu)確定了以后就要想動(dòng)態(tài)規(guī)劃的三要素了。樹(shù)型動(dòng)態(tài)規(guī)劃階段的具有共性：樹(shù)的層數(shù)，狀態(tài)是結(jié)點(diǎn)，但是只描述結(jié)點(diǎn)顯然不夠，需要在加一個(gè)參數(shù)。于是我們想到設(shè)計(jì)一個(gè)狀態(tài)opt[i,j]表示以i為跟的樹(shù)，選j個(gè)課程可獲得的最優(yōu)解。因?yàn)闃?shù)是以0為根的而0又必須要選所以問(wèn)題的解不是opt[0,m]而是opt[0,m+1]。決策是什么呢？對(duì)于二叉樹(shù)我在設(shè)計(jì)決策時(shí)習(xí)慣分類討論這樣結(jié)構(gòu)清晰。1這棵樹(shù)只有左子樹(shù)：要選左子樹(shù)中的課程，那么根結(jié)點(diǎn)一定要選，所以決策就是在左子樹(shù)中選j1個(gè)課程，在加上選根結(jié)點(diǎn)可獲得的分?jǐn)?shù)。2這棵樹(shù)只有右子樹(shù)： 因?yàn)橛易訕?shù)和根在原問(wèn)題中是兄弟關(guān)系，所以選右子樹(shù)中的課程未必要選根，這樣決策就有兩條：（1）在右子樹(shù)中選j個(gè)的最優(yōu)值。（2）在右子樹(shù)中選j1個(gè)的最優(yōu)值加上選根結(jié)點(diǎn)可獲得的分?jǐn)?shù)。3都有： 這種情況的決策很容易想到，從左子樹(shù)中選k1個(gè)，從右子樹(shù)中選jk個(gè)的最優(yōu)值加上根結(jié)點(diǎn)可獲得的分?jǐn)?shù)。 但要注意，當(dāng)K=1也就是左子樹(shù)選0個(gè)時(shí)，根結(jié)點(diǎn)可以不選，右子樹(shù)可以選j個(gè)而不是j1個(gè)；當(dāng)然根結(jié)點(diǎn)也可以選，選了根結(jié)點(diǎn)右子樹(shù)就得選j1個(gè)了。針對(duì)不同情況寫(xiě)出狀態(tài)轉(zhuǎn)移方程：max(opt[t[i].L,j1]+t[i].data) （只有左子樹(shù)）opt[i,j] = max(opt[t[i].r,j1]+t[i].data, opt[t[i].r,j]) （只有右子樹(shù)） max(opt[t[i].L,k1]+opt[t[i].r,jk]+t[i].data,opt[t[i].r,j])（都有） (1=k=j)時(shí)間復(fù)雜度： 狀態(tài)數(shù)O（NM）*轉(zhuǎn)移代價(jià)O（M）=O（NM2）注：（1）實(shí)際轉(zhuǎn)移代價(jià)比理論值小的多?！驹创a】program P1180。constmaxn=400。type treetype=record data,L,r:lon