選課 score.pas
學(xué)校實(shí)行學(xué)分制。每門(mén)的必修課都有固定的學(xué)分，同時(shí)還必須獲得相應(yīng)的選修課程學(xué)分。學(xué)校開(kāi)設(shè)了N（N<300）門(mén)的選修課程，每個(gè)學(xué)生可選課程的數(shù)量M是給定的。學(xué)生選修了這M門(mén)課并考核通過(guò)就能獲得相應(yīng)的學(xué)分。在選修課程中，有些課程可以直接選修，有些課程需要一定的基礎(chǔ)知識(shí)，必須在選了其它的一些課程的基礎(chǔ)上才能選修。例如《Frontpage》必須在選修了《Windows操作基礎(chǔ)》之后才能選修。我們稱(chēng)《Windows操作基礎(chǔ)》是《Frontpage》的先修課。每門(mén)課的直接先修課最多只有一門(mén)。兩門(mén)課也可能存在相同的先修課。每門(mén)課都有一個(gè)課號(hào)，依次為1，2，3，…。例如:
 
課號(hào) 先修課號(hào) 學(xué)分   
1 無(wú) 1   
2 1 1   
3 2 3   
4 無(wú) 3   
5 2 4 
 
 表中1是2的先修課，2是3、4的先修課。如果要選3，那么1和2都一定已被選修過(guò)。
你的任務(wù)是為自己確定一個(gè)選課方案，使得你能得到的學(xué)分最多，并且必須滿足先修課優(yōu)先的原則。假定課程之間不存在時(shí)間上的沖突。
程序名：score
輸入格式：
輸入文件的第一行包括兩個(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
 
【解析】
首先可以從題目中看出這是一類(lèi)樹(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],j-k]);0<=k<=j。f[right[i].j-k]表示右孩子只能選j-k門(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ī)劃很重要。
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 //在進(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,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.

問(wèn)題描述
幾乎整個(gè)Byteland王國(guó)都被森林和河流所覆蓋。小點(diǎn)的河匯聚到一起，形成了稍大點(diǎn)的河。就這樣，所有的河水都匯聚并流進(jìn)了一條大河，最后這條大河流進(jìn)了大海。這條大河的入海口處有一個(gè)村莊——名叫Bytetown。
在Byteland國(guó)，有n個(gè)伐木的村莊，這些村莊都座落在河邊。目前在Bytetown，有一個(gè)巨大的伐木場(chǎng)，它處理著全國(guó)砍下的所有木料。 木料被砍下后，順著河流而被運(yùn)到Bytetown的伐木場(chǎng)。Byteland的國(guó)王決定，為了減少運(yùn)輸木料的費(fèi)用，再額外地建造k個(gè)伐木場(chǎng)。這k個(gè)伐木場(chǎng)將被建在其他村莊里。這些伐木場(chǎng)建造后，木料就不用都被送到Bytetown了，它們可以在 運(yùn)輸過(guò)程中第一個(gè)碰到的新伐木場(chǎng)被處理。 顯然，如果伐木場(chǎng)座落的那個(gè)村子就不用再付運(yùn)送木料的費(fèi)用了。它們可以直接被本村的伐木場(chǎng)處理。
注意：所有的河流都不會(huì)分叉，也就是說(shuō)，每一個(gè)村子，順流而下都只有一條路——到bytetown。
國(guó)王的大臣計(jì)算出了每個(gè)村子每年要產(chǎn)多少木料，你的任務(wù)是決定在哪些村子建設(shè)伐木場(chǎng)能獲得最小的運(yùn)費(fèi)。其中運(yùn)費(fèi)的計(jì)算方法為：每一塊木料每千米1分錢(qián)。

    編一個(gè)程序：
1．從文件讀入 村子的個(gè)數(shù)，另外要建設(shè)的伐木場(chǎng)的數(shù)目，每年每個(gè)村子產(chǎn)的木料的塊數(shù)以及河流的描述。
2．計(jì)算最小的運(yùn)費(fèi)并輸出。
輸入輸出
第一行 包括兩個(gè)數(shù) n（2<=n<=100），k（1<=k<=50,且 k<=n）。n為村莊數(shù)，k為要建的伐木場(chǎng)的數(shù)目。除了bytetown外，每個(gè)村子依次被命名為1，2，3……n，bytetown被命名為0。
接下來(lái)n行，每行包涵3個(gè)整數(shù)
wi——每年i村子產(chǎn)的木料的塊數(shù)0020（0<=wi<=10000）
vi——離i村子下游最近的村子（或bytetown）（0<=vi<=n）
di——vi到i的距離(km)。（1<=di<=10000）

輸出包含一行，即最小的運(yùn)費(fèi)。

保證每年所有的木料流到bytetown的運(yùn)費(fèi)不超過(guò)2000，000，000分
50％的數(shù)據(jù)中 n不超過(guò)20。
 
【解析】
此題很明顯的是一個(gè)樹(shù)形動(dòng)態(tài)規(guī)劃題。
定義F[I,J,Fa]代表以I節(jié)點(diǎn)為根的子樹(shù)，新增J個(gè)木材處理廠，離它最近的木材處理廠是Fa，，有如下方程：
F[I,J,Fa]:=Min{F[Left[I],K,Fa]+F[Right[I],J-K,Fa]+Cost[I]*(Dis[I]-Dis[Fa])，F(xiàn)[Left[I],K,I]+F[Right[I],J-K-1,Fa]}
仍然用左孩子右兄弟來(lái)實(shí)現(xiàn)多叉轉(zhuǎn)二叉。需要提前預(yù)處理出來(lái)一點(diǎn)到其余各點(diǎn)間的距離。
 
program river;
const
   filename='river';
type
   xx=record
      l,r,w:longint;
   end;
   node=record //記錄以i為根的所有結(jié)點(diǎn)信息
      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個(gè)伐木場(chǎng)，且離s最近的點(diǎn)為k時(shí)的最優(yōu)值
   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); //預(yù)處理一點(diǎn)到其余各點(diǎn)間的距離
var
   i:longint;
begin
   dis[x]:=s;
   for i:=1 to a[x].num do //所有與x相連的結(jié)點(diǎn)
      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個(gè)伐木場(chǎng)，且離s最近的點(diǎn)為k時(shí)的最優(yōu)值
var
   i,j:longint;
begin
   if s<0 then
      begin
         f[s,k,p]:=0;
         exit;
      end;
   if flag[s,k,p] then exit; //不重復(fù)搜索
   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處不設(shè)置伐木場(chǎng)的狀態(tài)
         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處設(shè)置伐木場(chǎng)的狀態(tài)
            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.
沒(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 7
　　又是求最優(yōu)解，并且每一個(gè)節(jié)點(diǎn)的取舍關(guān)乎到全局 因此，此題可用樹(shù)形動(dòng)態(tài)規(guī)劃
　　我們可用f[v][0]存儲(chǔ)不選編號(hào)為V的節(jié)點(diǎn)的最優(yōu)解，f[v][1]存儲(chǔ)選編號(hào)為V的節(jié)點(diǎn)的最優(yōu)解
　　#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存儲(chǔ)每個(gè)人的氣氛值，shs存儲(chǔ)每個(gè)人的上司，xb存儲(chǔ)沒(méi)個(gè)人的下屬，shu存儲(chǔ)構(gòu)成的樹(shù)
　　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;
　　}//建樹(shù),maxc存儲(chǔ)最大層數(shù)
　　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;
　　}//動(dòng)態(tài)轉(zhuǎn)移方程
　　}
　　}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;
　　}//從頂頭上司那里擇優(yōu)選擇
　　cout<<s<<endl;
　　system("pause");
　　return 0;
　　}