|
選課 score.pas
學(xué)校實(shí)行學(xué)分制。每門的必修課都有固定的學(xué)分，同時(shí)還必須獲得相應(yīng)的選修課程學(xué)分。學(xué)校開設(shè)了N（N<300）門的選修課程，每個(gè)學(xué)生可選課程的數(shù)量M是給定的。學(xué)生選修了這M門課并考核通過(guò)就能獲得相應(yīng)的學(xué)分。在選修課程中，有些課程可以直接選修，有些課程需要一定的基礎(chǔ)知識(shí)，必須在選了其它的一些課程的基礎(chǔ)上才能選修。例如《Frontpage》必須在選修了《Windows操作基礎(chǔ)》之后才能選修。我們稱《Windows操作基礎(chǔ)》是《Frontpage》的先修課。每門課的直接先修課最多只有一門。兩門課也可能存在相同的先修課。每門課都有一個(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è)空格隔開），其中1≤N≤300,1≤M≤N。 以下N行每行代表一門課。課號(hào)依次為1，2，…，N。每行有兩個(gè)數(shù)（用一個(gè)空格隔開），第一個(gè)數(shù)為這門課先修課的課號(hào)（若不存在先修課則該項(xiàng)為0），第二個(gè)數(shù)為這門課的學(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 【解析】 首先可以從題目中看出這是一類樹形動(dòng)態(tài)規(guī)劃題。為了方便儲(chǔ)存，可以將多叉樹轉(zhuǎn)化為二叉樹，常用的表示方法是左孩子右兄弟表示法。設(shè)f[i,j]表示以i為節(jié)點(diǎn)選j門課所獲得的最大學(xué)分，則f[I,J]:=max(f[left[i],k]+f[right[i],j-k]);0<=k<=j。f[right[i].j-k]表示右孩子只能選j-k門課。以-oo表示空節(jié)點(diǎn)，0表示根節(jié)點(diǎn)，1~n是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分錢。 編一個(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è)樹形動(dòng)態(tài)規(guī)劃題。 定義F[I,J,Fa]代表以I節(jié)點(diǎn)為根的子樹，新增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è)人不受他的直接上司約束而能玩得開心，公司領(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行的書表示第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)成一棵樹。 5 | \ 3 4 | \ | \ 1 2 6 7 又是求最優(yōu)解，并且每一個(gè)節(jié)點(diǎn)的取舍關(guān)乎到全局 因此，此題可用樹形動(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)成的樹 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存儲(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; } |
|
|
