NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC高中組 » NPSC2008高中組決賽
 NPSC 2008 高中組 決賽 C.咒語

作者 主題: NPSC 2008 高中組 決賽 C.咒語  (閱讀 2043 次)

sagit

  • 管理員
  • 白金會員
  • *****
  • 文章數: 231
    • 檢視個人資料
NPSC 2008 高中組 決賽 C.咒語
« 於: 十一月 30, 2009, 01:52:35 pm »

NPSC 2008 高中組 決賽 C.咒語

說明:給你一個邊有權重的無向圖,請你找出一條從起點走到終點權重最大的路徑,中間經過的點的編號必須依照順序,也就是說從1走到n,中間某些點可以跳過不走,但順序一定是編號小的在前面。

解法:動態規劃(DP)解,我們可以設一個陣列 Ans[] 記錄走到該點的最大權重,當我們只考慮 k 點的前一個點的編號,則可以得到: Ans[k] 的值為 Ans[j]+W[j][k] (0<=j<k) 的最大值,其中 W[j][k] 代表從 j 點到 k 點這條邊的權重。為了加快處理速度,我們只處理權重大於 0 的邊,因為 Ans[] 的值是遞增的,所以邊的權重為 0 的情況其最大值為 Ans[k-1],只要處理這個就行了。

參考程式:(By sagit)

代碼: [選擇]
// NPSC 2008 高中組決賽
// 題目 C - 咒語
// By sagit at TCGS
#include <cstdlib>
#include <iostream>
#include <deque>

using namespace std;

const int MAX=10001;
deque<int> Y[MAX], Z[MAX];              // Y 記錄前一個點, Z 記錄該通道人數
int Ans[MAX];                           // 記錄到該點為止可以遇到的最大人數

int main()
{
    freopen("pc.in", "rt", stdin);
    freopen("pc.out", "w+t", stdout);
    ios_base::sync_with_stdio(false);
    int n, m, i, j, x, y, z, t;
    while (1)
    {
        cin >> n >> m;
        if ( n==0 && m==0 ) break;
        for (i=0; i<n; i++)             // 啟始化
        {
            Y[i].clear();
            Z[i].clear();
        }
        for (i=0; i<m; i++)             // 記錄前一個點到該點可遇到的人數
        {
            cin >> x >> y >> z;
            if ( x<y ) { t=x; x=y; y=t; }
            Y[x].push_back(y);
            Z[x].push_back(z);
        }
        for (i=1, Ans[0]=0; i<n; i++)   // 尋找以 j 為中間點可遇到的最大人數
        {
            for (j=0, z=Ans[i-1]; j<Y[i].size(); j++)
            {
                x=Ans[Y[i][j]]+Z[i][j];
                if (x>z) z=x;
            }
            Ans[i]=z;
        }
        cout << Ans[n-1] << endl;
    }
//    system("PAUSE");
    return 0;
}
記錄

lini

  • 高級會員
  • ****
  • 文章數: 101
    • 檢視個人資料
回覆: NPSC 2008 高中組 決賽 C.咒語
« 回覆 #1 於: 五月 10, 2010, 09:05:47 pm »

題目寫錯了 ..

(1) a1=0, ak=n

應該是 n-1
記錄
+ NPSC補完計劃 » NPSC高中組 » NPSC2008高中組決賽
 NPSC 2008 高中組 決賽 C.咒語