描述
大戈壁越野赛前后分为很多赛段，一个车队也有多辆车。一个车队在一个赛段只能使用一辆车，但是到达赛段中转站（分隔各赛段的点）时可以任意更换车辆，当然也可以不换。在不同赛段，不同的车有着不同的表现，如果规则不限定换车次数，显然可以在每一个赛段都用最好用的车，但很不幸，换车次数有限定，那么，安排一个合理的换车策略十分重要。我们认为，车队可以选择任意一种车开始赛程，不算换车次数。
现在依次给出从起点到终点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
动态规划算法.
F[i][k][j]表示前i个赛道,换了k次,最后一次使用的是车j,所能达到的最快速度.
A[i][j]存储第i个赛道,第j量车的时间.
那么,要么前一次使用的也是车j,那么不算换车,得到:
或者,前一次使用的不是车j,而是车a(1<a<M),那么换车次数+1,得到:
那么最终的动态规划方程为:
注意点:
1.动态规划初始条件的设置.
2.用scanf与printf,用cin与cout会超时.
AC程序如下:
#include<iostream>
using namespace std;
#define maxn 10002
#define maxm 12
#define maxq 102
#define MM 999999
int f[maxn][maxq][maxm];
int A[maxn][maxm];
int main()
{
int N,M,Q;
scanf("%d%d%d",&N,&M,&Q);
for(int i=1;i<=M;i++)
{
for(int j=1;j<=N;j++)
{
scanf("%d",&A[j][i]);
}
}
for(int i=1;i<=N;i++)
{
f[i][0][0]=MM;
}
for(int j=0;j<=M;j++)
{
f[0][0][j]=MM;
}
for(int i=0;i<=N;i++)
{
for(int k=1;k<=Q;k++)
{
for(int j=0;j<=M;j++)
f[i][k][j]=MM;
}
}
for(int i=1;i<=N;i++)
{
for(int j=1;j<=M;j++)
{
f[0][0][j]=0;
f[i][0][j]=f[i-1][0][j]+A[i][j];
}
}
for(int j=0;j<=M;j++)
{
f[0][0][j]=MM;
}
for(int i=2;i<=N;i++)
{
for(int k=1;k<=Q&&k<i;k++)
{
for(int j=1;j<=M;j++)
{
int maxx=99999999;
for(int l=1;l<=M;l++)
{
if(l!=j&&maxx>f[i-1][k-1][l])
maxx=f[i-1][k-1][l];
}
f[i][k][j]=min(f[i-1][k][j],maxx)+A[i][j];
}
}
}
int maxx=99999999;
for(int i=0;i<=Q;i++)
{
for(int j=1;j<=M;j++)
{
if(maxx>f[N][i][j])
maxx=f[N][i][j];
}
}
printf("%d\n",maxx);
return 0;
}
acm.njupt--1859,布布扣,bubuko.com
原文：http://blog.csdn.net/ice110956/article/details/20281345