【アルゴリズム設計とデータ構造】ダイナミック企画入門——URAL 1119 Metro

15203 ワード

テーマリンク
http://acm.timus.ru/problem.aspx?space=1&num=1119
テーマの内容
1119メトロ
Time limit:0.5 second
Memory limit:64 MB
Manof SKB Korntur programmers like to work by Metro because the main office is situted quite close the station Uralmash.So,since a sedentary requires active exercises off-duty,manthe of the stalfone-Night

【算法设计与数据结构】动态规划入门——URAL 1119 Metro_第1张图片

Problem illustration Nikifor lives in parts of our city where steets form a gride of redential quarters.All the quarters ares es with side 100 meters.A Metro entrance is situted one of the crossroads.Nil the forwarthstarting from his home,walks along the street leading eigher to the north or to the east.On his way he may cross some quarters diagonally from their south-western coners to the north-eatern.the.Thators.how long is the shotest route.You are to write a program that will calculate the length of the shotest route from the south-wester n coner of the grid to the north-eaterone.
Input Theare two integers in the first line:N and M(0Output Your program is to output a length of the shotest rout Nikifor's home to the Metro station in meters,rounded to the integer amount of meters.
Sample
input
out put
3 2
383
3
1
3 2
1 2
タイトルの大意
都市は正方形の格子で、各格子の辺の長さは100メートルです.地下鉄駅はその交差点の一つです.ニカノは家から地下鉄駅まで歩いて行きます.彼は道に沿って歩いて、いくつかの格子の対角線を通り抜けることができて、このように少し近くなります.Nikanorは西南角の家から東北角の地下鉄駅までの最短ルートを求めます.
考え方
逆数から二番目のステップの点iから始点までの最短距離がd[n-1][i]であると仮定すると、ans=min｛d[n-1]、[i]＋最終ステップの距離｝となる.(一歩ごとの距離はもう分かりました.)問題:実際にはd[n-1][i]の値は分かりません.問題は出発点から点iまでの最短距離を求めることになります.同じ道理でd[n-2]、[i]に助けを求めます.最終的には最初の点から出発点までの最短距離を求めます.結論:トップから下の分析、ボトムから上への計算――動的計画解;状態移行方程式:

if (    )
    dp[i][j] = min{dp[i][j-1]+100, dp[i-1][j]+100, dp[i-1][j-1]+sqrt(20000)};
else
    dp[i][j] = min{dp[i][j-1]+100, dp[i-1][j]+100};

アルゴリズムステップ
1)境界を初期化する:

dp[0][0] = 0; 
for (int i = 1; i <= n; i++) dp[i][0] = dp[i-1][0] + 100; for (int i = 1; i <= m; i++) dp[0][i] = dp[0][i-1] + 100;

2)底から上に向かって解く:

for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
    { if (diag[i][j]) dp[i][j] = min{dp[i][j-1]+100, dp[i-1][j]+100, dp[i-1][j-1]+sqrt(20000)};
        else
            dp[i][j] = min{dp[i][j-1]+100, dp[i-1][j]+100};
    }

タイトルソースコード

#include<iostream>
#include<string>
#include<cmath>
#include<vector>
#include<algorithm>

using namespace std;

double dp[1001][1001];
bool diag[1001][1001];

double min(const double &a, const double &b, const double &c)
{
    double min = a<b?a:b;
    return min<c?min:c;
}

int main()
{
    int n,m;
    cin>>n>>m;
    int k;
    cin>>k;
    for (int i = 0; i <= n; i++)
        for(int j = 0; j <=m; j++)
            diag[i][j] = false;
    for (int i = 0; i < k; i++)
    {
        int x, y;
        cin>>x>>y;
        diag[x][y] = true;
    }
    dp[0][0] = 0;
    for (int i = 1; i <= n; i++)
        dp[i][0] = dp[i-1][0] + 100;
    for (int i = 1; i <= m; i++)
        dp[0][i] = dp[0][i-1] + 100;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            if (diag[i][j])
                dp[i][j] = min(dp[i-1][j]+100, dp[i][j-1]+100, dp[i-1][j-1]+sqrt(20000.0));
            else
                dp[i][j] = min(dp[i-1][j]+100, dp[i][j-1]+100, 999999999.0);     
        }
    cout<<floor(dp[n][m]+0.5)<<endl;
    return 0;
}

スペース最適化
dp[i][j]を計算するときは、dp[i-1][j]またはdp[i]、[j-1]またはdp[i-1]、[j-1]を使うだけで、他の以前の計算結果は不要です.この特徴から、一次元配列で問題を見ることができます.

for (int i = 1; i <= m; i++) 
    for (int j = 1; j <= n; j++) 
        dp[j] = min (dp[j], dp[j-1]) + 100;

実際、ここのdp[j-1]はdp[i][j-1]を表し、dp[j]はdp[i-1][j]を表しています.一次元配列でdp[i-1][j-1]を表すにはどうすればいいですか?下記のコードを見てください.

for (int i = 1; i <= m; i++) 
{
    double t = dp[0];
    for (int j = 1; j <= n; j++) 
    {
        double a = dp[j];  
        if (    )
               dp[j] = min (dp[j]+100, dp[j-1]+100,t+sqrt(20000));
        else
            dp[j] = min (dp[j], dp[j-1]) + 100;
        t = a;
    } 
}

上記のコードの中で、aに保存されているのはdp[i-1][j]であり、今回のループの最後にtに値を割り当て、tは次のサイクルで使用されます.j++のため、次のサイクルでは、tはdp[i-1][j-1]を表します.これまで,2次元配列の代わりに1次元配列を用いることで,空間複雑度最適化の目的を達成し,最適化後の空間複雑度はO(n)であった.
最適化後のコード

#include<iostream>
#include<string>
#include<cmath>
#include<vector>
#include<algorithm>

using namespace std;

double dp[1001];
bool diag[1001][1001];

double min(const double &a, const double &b, const double &c)
{
    double min = a<b?a:b;
    return min<c?min:c;
}

int main()
{
    int n,m;
    cin>>n>>m;
    int k;
    cin>>k;
    for (int i = 0; i <= n; i++)
        for(int j = 0; j <=m; j++)
            diag[i][j] = false;
    for (int i = 0; i < k; i++)
    {
        int x, y;
        cin>>x>>y;
        diag[x][y] = true;
    }
    for (int i = 0; i <= n; i++) 
        dp[i] = i*100;
    for (int i = 1; i <= m; i++) 
    {       
        double t = dp[0];
        dp[0] += 100;
        for (int j = 1; j <= n; j++) 
        {
            double a = dp[j];  
            if (diag[j][i])
                   dp[j] = min(dp[j]+100, dp[j-1]+100,t+sqrt(20000.0));
            else
                   dp[j] = min(dp[j], dp[j-1], 999999999.0) + 100;
            t = a;
        } 
    }
    cout<<floor(dp[n]+0.5)<<endl;
    return 0;
}

Hding the Progress Bar of a.NET 2.0 CF WebBrowse

javaはcmdコマンドを呼び出します.どうやってYボタンを入力するかをシミュレーションします.