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