1262：【例9.6】挖地雷

時間限制: 1000 ms ??? ??? 內存限制: 65536 KB
提交數: 9596 ??? 通過數: 4628

【題目描述】

在一個地圖上有nn個地窖（n≤200）,每個地窖中埋有一定數量的地雷。同時，給出地窖之間的連接路徑，并規定路徑都是單向的,且保證都是小序號地窖指向大序號地窖，也不存在可以從一個地窖出發經過若干地窖后又回到原來地窖的路徑。某人可以從任意一處開始挖地雷，然后沿著指出的連接往下挖（僅能選擇一條路徑），當無連接時挖地雷工作結束。設計一個挖地雷的方案，使他能挖到最多的地雷。

【輸入】

第一行：地窖的個數；

第二行：為依次每個地窖地雷的個數；

下面若干行：

xi yi? ?//表示從 xi 可到 yi，xi<yi。

最后一行為"00"表示結束。

【輸出】

k1?k2?…?kv? ? //挖地雷的順序

挖到最多的雷。

【輸入樣例】

6 5 10 20 5 4 5 1 2 1 4 2 4 3 4 4 5 4 6 5 6 0 0

【輸出樣例】

3-4-5-6 34

【分析】

? ? ? ? 設a[i]存儲地窖中地雷數，f[i]以第i個地窖為起點最多可以挖到的地雷數，p[i]記錄后續地窖位置。逆推實現。

（1）劃分階段。

? ? ? ? 階段：按地窖編號劃分階段；樣例中共有6個階段。

（2）確定狀態和狀態變量。

? ? ? ? 狀態：按地窖編號劃分狀態。狀態信息用f[i]表示。

（2）確定決策并寫出狀態轉移方程。

? ? ? ? f[i]的值從哪來？當然是從后面f[i]來。決策：后面有通路的地窖中，選可以挖到地雷數最多的那個，策略：最多地雷數。故，狀態轉移方程： f[i]=max{ a[i]+f[j]?| c[i][j]=1, i<j<=n }。

（4）尋找邊界條件。

? ? ? ? 逆推時， 邊界：f[n]=a[n]。目標：max{ f[i] | 1<=i<=n }。?

（5）設計并實現程序。數據存儲和問題求解過程如下：

?【參考代碼】

#include <stdio.h> #define N 210 int n; int x,y; int a[N]; // 每個地窖的地雷數 int c[N][N]; // 兩個地窖中是否有通路 int f[N]; // 以第i個地窖為起點最多可挖到的地雷數 int p[N]; // 后續地窖的位置 int ans,s; // ans最大的地雷數，s路徑起點編號 int main() {int i,j;int maxn,k;scanf("%d",&n);for(i=1;i<=n;i++) //輸入每個地窖中的地雷數 scanf("%d",&a[i]);while(scanf("%d%d",&x,&y) && x||y){c[x][y]=1; //1連通，0不連通}f[n]=a[n]; // 邊界for(i=n-1;i>=1;i--){k=0;maxn=0;for(j=i+1;j<=n;j++){if(c[i][j]==1 && f[j]>maxn){maxn=f[j];k=j;}}f[i]=a[i]+maxn;p[i]=k;}ans=f[1];s=1;for(i=2;i<=n;i++) //找f[i]中的最大值 {if(f[i]>ans){ans=f[i];s=i;}}while(p[s]!=0) //輸出挖雷順序 {printf("%d-",s);s=p[s];}printf("%d\n",s);printf("%d\n",ans);return 0; }

http://ybt.ssoier.cn:8088/problem_show.php?pid=1262

總結

以上是生活随笔為你收集整理的信息学奥赛一本通（1262：【例9.6】挖地雷）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。