程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu 4824 Disk Schedule雙調歐幾裡得旅行商問題(dp)

hdu 4824 Disk Schedule雙調歐幾裡得旅行商問題(dp)

編輯：C++入門知識

Disk Schedule

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 153 Accepted Submission(s): 86

Problem Description 有很多從磁盤讀取數據的需求，包括順序讀取、隨機讀取。為了提高效率，需要人為安排磁盤讀取。然而，在現實中，這種做法很復雜。我們考慮一個相對簡單的場景。
磁盤有許多軌道，每個軌道有許多扇區，用於存儲數據。當我們想在特定扇區來讀取數據時，磁頭需要跳轉到特定的軌道、具體扇區進行讀取操作。為了簡單，我們假設磁頭可以在某個軌道順時針或逆時針勻速旋轉，旋轉一周的時間是360個單位時間。磁頭也可以隨意移動到某個軌道進行讀取，每跳轉到一個相鄰軌道的時間為400個單位時間，跳轉前後磁頭所在扇區位置不變。一次讀取數據的時間為10個單位時間，讀取前後磁頭所在的扇區位置不變。磁頭同時只能做一件事：跳轉軌道，旋轉或讀取。
現在，需要在磁盤讀取一組數據，假設每個軌道至多有一個讀取請求，這個讀取的扇區是軌道上分布在 0到359內的一個整數點扇區，即軌道的某個360等分點。磁頭的起始點在0軌道0扇區，此時沒有數據讀取。在完成所有讀取後，磁頭需要回到0軌道0扇區的始點位置。請問完成給定的讀取所需的最小時間。

Input 輸入的第一行包含一個整數M（0 對於每組測試數據，第一行包含一個整數N（0
Output 對於每組測試數據，輸出一個整數，表示完成全部讀取所需的時間。
Sample Input

Sample Output

830
4090
1642

Source 2014年百度之星程序設計大賽 - 資格賽
Recommend liuyiding

思路【轉】：歐幾裡得旅行商問題是對平面上給定的n個點確定一條連接各點的最短閉合旅程的問題。如圖（a）給出了一個7個點問題的解。這個問題的一般形式是NP完全的，故其解需要多於多項式的時間。

J.L. Bentley 建議通過只考慮雙調旅程(bitonic tour)來簡化問題,這種旅程即為從最左點開始，嚴格地從左到右直至最右點，然後嚴格地從右到左直至出發點。下圖(b)顯示了同樣的7個點的最短雙調路線。在這種情況下，多項式的算法是可能的。事實上，存在確定的最優雙調路線的O(n*n)時間的算法。

圖a 圖b<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+16I61NrSu7j2taXOu9WkJiMyNjY4NDvJz8/Uyr61xMa9w+bJz7XExt+49rXjoaMgYSnX7rbMsdW6z8K3z98ss6S2yLTz1LzKxzI0Ljg5oaPV4rj2wrfP37K7ysfLq7X3tcSho2Ipz+DNrLXjtcS8r7rPyc+1xNfutszLq7X3sdW6z8K3z9+ho7Oktsi089S8yscyNS41OKGjPC9wPgo8cD7V4srH0ru49svjtbzJz7XEy7y/vMziMTUtMaGjPC9wPgo8cD7K18/Ivau4+LP2tcS148XF0PKjrLnYvPzX1nijrNbY0MKx4LrFo6y009fz1sHT0jGjrDKjrDOjrKGto6xuoaM8L3A+CjxwPrao0uVwW2ldW2pdo6yx7cq+veG142m1vb3hteNq1q685LXEvuDA66GjPC9wPgo8cD62qNLlZFtpXVtqXaOsse3KvrTTacGstb0xo6zU2bTTMcGstb1qo6yjqNei0uKjrGk+aqOsx9KyosO709DP4MGsoaOjqTwvcD4KPHA+PGltZyBzcmM9"http://www.2cto.com/uploadfile/Collfiles/20140526/20140526091425235.png" alt="\">

對於任意一個點i來說，有兩種連接方法，一種是如圖（a）所示，i與i-1相連，另一種呢是如圖（b），i與i-1不相連。

根據雙調旅程，我們知道結點n一定與n相連，那麼，如果我們求的d[n][n-1]，只需將其加上p[n-1][n]就是最短雙調閉合路線。

根據上圖，很容易寫出方程式：

dp[i][j]=dp[i-1][j]+dist[i][i-1];

dp[i][i-1]=min(dp[i][i-1],dp[i-1][j]+dist[j][i]);

/*************************************************************************
	> File Name: hdu-4824-Disk_Schedule.cpp
	> Author: nealgavin
	> Mail: [email protected] 
	> Created Time: Sun 25 May 2014 07:38:59 PM CST
 ************************************************************************/

#include
#include 
#include 

using namespace std;

const int mm = 1000+9;
const int oo = 1e9;

int dp[mm][mm],d[mm];
int n;

int dis(int x,int y)
{
    if(d[x] < d[y])
        x^=y^=x^=y;
    int distance = d[x]-d[y];
    return min(distance,360-distance);
}

void init()
{
    dp[1][0] = dis(0,1);
}

int DP()
{
    for(int i=2;i<=n;++i)
    {
        dp[i][i-1] = oo;
        for(int j=0;j