首页 > 代码库 > NOJ1859 越野赛 三维DP
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 <cstdio> #include <cstring> #include <cmath> #include <algorithm> #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; }
NOJ1859 越野赛 三维DP