题解 P3399 【丝绸之路】
wzxx
2017-12-31 18:03:20
#### 动态规划（两个版本）
------------
先分析一下题目。
1. 所有城市连起来是一条链。
1. 每一天有走和不走两种选择。
仅凭这两点，我们就很容易想到dp的思路。我写了两个版本，一个是龟速版，总用时2000多ms；一个是飞速版，总用时8ms......
------------
先说说龟速的把。设状态f[i][j]表示第j天 **到达** 第i个城市的最小疲劳值，也就是说这一天你必须是刚好从前一个城市走到这里来的。状态转移方程就很容易推出来了，就是找上一个城市在i-1..j-1天里哪天到达的疲劳值最小，然后再加上这一天从上一个城市到达这一个城市的疲劳值。为什么是i-1..j-1而不是1..j-1呢？因为第i-1个城市最早只能在第i-1天到达，继续找前面的完全就没有必要。想一想，第3个城市能在第2天到达吗？当然不行。
上述文字用公式表达就是这个样子：
f[i][j]=min{f[i-1][i-1..j-1]}+D[i]\*C[j]
为什么这个公式就可以成立呢？因为你找到了哪一天到达上一个城市的疲劳值最小，你就可以不停地休息（休息是不会增加疲劳值的），一直休息到第j天，再走过来，这样就是最优的了。
代码：
```cpp
#include<iostream>
#include<cstdio>
#include<fstream>
#include<algorithm>
#include<string>
#include<sstream>
#include<cstring>
using namespace std;
const int INF=2139063143;
int D[1002],C[1002],f[1002][1002];
int main()
{
memset(f,0x7f,sizeof(f));
int N=0,M=0;
scanf("%d%d",&N,&M);
for(int i=1;i<=N;i++) scanf("%d",&D[i]);
for(int i=1;i<=M;i++)
{
scanf("%d",&C[i]);
f[1][i]=D[1]*C[i];//初始化第一个城市的
}
for(int i=2;i<=N;i++)
for(int j=i;j<=M;j++)
{
int Min=INF;
//找最小
for(int k=j-1;k>=i-1;k--) Min=min(Min,f[i-1][k]);
f[i][j]=Min+D[i]*C[j];//更新
}
int ans=INF;
for(int i=N;i<=M;i++) ans=min(ans,f[N][i]);
printf("%d",ans);
return 0;
}
```
------------
接着再说一下快速的吧。设状态f[i][j]表示第j天 **位于** 第i个城市的最小疲劳值，也就是说这一天你可以不是刚好从前一个城市走到这里来的，也可以是前几天已经到了，休息到今天的。再看题目，对于每一天都有走和不走两种选择，状态转移方程就出来了。对于在第i个城市的第j天，你可以在j-1天从上一个城市走过来（第1种选择），也可以休息不走（第2种选择）。这里和龟速版的意思一样，也是看一看从上一个城市的哪一天走过来最优，只不过可以休息。
上述文字用公式表达就是这样子：
f[i][j]=min{f[i][j-1],f[i-1][j-1]+D[i]\*C[j]}
其中f[i][j-1]是休息，f[i-1][j-1]+D[i]\*C[j]是走。
代码：
```cpp
#include<iostream>
#include<cstdio>
#include<fstream>
#include<algorithm>
#include<string>
#include<sstream>
#include<cstring>
using namespace std;
const int INF=2139063143;
int D[1002],C[1002],f[1002][1002];
int main()
{
int N=0,M=0;
scanf("%d%d",&N,&M);
for(int i=1;i<=N;i++) scanf("%d",&D[i]);
for(int i=1;i<=M;i++) scanf("%d",&C[i]);
memset(f,0x7f,sizeof(f));
for(int i=0;i<=M;i++) f[0][i]=0;
for(int i=1;i<=N;i++)
for(int j=i;j<=M;j++)
f[i][j]=min(f[i][j-1],f[i-1][j-1]+D[i]*C[j]);
int ans=INF;
for(int i=N;i<=M;i++) ans=min(ans,f[N][i]);
printf("%d",ans);
return 0;
}
```
------------
两种方案，个人感觉第一种好理解一点，但速度真的超级慢啊，大家自行取舍吧。