程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> NOJ1859 越野賽 三維DP

NOJ1859 越野賽 三維DP

編輯:C++入門知識

NOJ1859 越野賽 三維DP


題目描述

大戈壁越野賽前後分為很多賽段,一個車隊也有多輛車。一個車隊在一個賽段只能使用一輛車,但是到達賽段中轉站(分隔各賽段的點)時可以任意更換車輛,當然也可以不換。在不同賽段,不同的車有著不同的表現,如果規則不限定換車次數,顯然可以在每一個賽段都用最好用的車,但很不幸,換車次數有限定,那麼,安排一個合理的換車策略十分重要。我們認為,車隊可以選擇任意一種車開始賽程,不算換車次數。
現在依次給出從起點到終點N個賽段中每輛車的表現(跑完當前賽段所需時間),請計算出跑完全部賽程所需最短時間

輸入

第一行包含三個正整數N、M、Q,分別表示賽段數、車隊用車種類、最大更換車輛次數限制(1≤N≤10000,1≤M≤10,1≤Q≤100)。
接下來M行,每行N個正整數。第i行第j個數表示i號車在第j賽段的表現(這輛車跑完這個賽段所需時間),每個賽段的時間上限保證不超過1000。

輸出

輸出一行,包含一個整數,表示車隊在規則限定內的賽程最短完成時間


輸入樣例

3 2 1
1 4 1
2 2 3

輸出樣例

5



解題思路

三維DP dp[i][j][k]數組表示到i段賽道,換了j次車,最後選擇的車是k車的最小時間

假設我們現在已經考慮過前(i-1)段賽道 現在考慮第i段賽道。

如果在第i段賽道不換車 那麼d[i][j][k] = d[i-1][j][k] + speed[i][k];

如果在第i段賽道換車 那麼d[i][j][k] = min(d[i-1][j-1][x]) + speed[i][k]; (x不等於k)

把兩個式子合在一起 則 d[i][j][k] = min(d[i-1][j][k] , d[i-1][j-1][x](x不等於k)) + speed[i][k]

最後的答案應該是min(d[賽道數][x][y])


下面考慮一下初始化........

可以看出(i,j)狀態是由(i-1,j)和(i-1,j-1)這兩個狀態推出的 所以外循環遍歷i 內循環遍歷j 再在裡面遍歷k.

所以我們要初始化i = 1 和 j = 0的情況.....

詳見代碼


#include 
#include 
#include 
#include 
#define INF 1000000010
const int max_saidao = 10010;
const int max_che = 15;
const int max_huanche = 105;
using namespace std;
int speed[max_saidao][max_che];//speed[i][j]表示第i個賽道 第j輛車的速度
int dp[max_saidao][max_huanche][max_che];//dp[i][j][k]表示前i個賽道換了j次 最後使用的車是k  的最短時間
int main()
{
    int saidao,che,huanche;
    scanf("%d%d%d",&saidao,&che,&huanche);
    for(int i = 1 ; i <= che ; i ++) {
        for(int j = 1 ; j <= saidao ; j ++) scanf("%d",&speed[j][i]);
    }
    for(int i = 0 ; i <= saidao ; i ++) {
        for(int j = 0 ; j <= huanche ; j ++) {
            for(int k = 0 ; k <= che ; k ++) dp[i][j][k] = INF;
        }
    }
    //初始化dp[1][0][x]
    for(int i = 1 ;i <= che ; i ++) dp[1][0][i] = speed[1][i];
    //初始化dp[x][0][x]
    for(int i = 1 ;i <= che ; i ++) {//第i輛車,不換
        for(int j = 2 ; j <= saidao ; j ++) {
            dp[j][0][i] = dp[j-1][0][i] + speed[j][i];
        }
    }

    //dp
    for(int i = 2 ; i <= saidao ; i ++) {
        for(int j = 1 ; j <= huanche && j < i ; j ++) {
            for(int k = 1 ; k <= che ; k ++) {
                int _min = INF;
                for(int p = 1 ; p <= che ; p ++) {
                    if(p != k) if(_min > dp[i-1][j-1][p]) _min = dp[i-1][j-1][p];
                }
                if(_min > dp[i-1][j][k]) _min = dp[i-1][j][k];
                dp[i][j][k] = _min + speed[i][k];
            }
        }
    }

    //輸出dp[saidao][x][y]中最小的
    int _min = INF;
    for(int i = 0 ; i <= huanche ; i ++) {
        for(int j = 1 ; j <= che ; j ++) {
            if(_min > dp[saidao][i][j]) _min = dp[saidao][i][j];
        }
    }
    printf("%d\n",_min);
    return 0;
}


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved