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;
}