题解 P4009 【汽车加油行驶问题】 DP做法
wjyyy
2018-07-05 16:26:41
[欢迎来我的blog食用](http://www.wjyyy.top/728.html)
### 它真的是网络流24题吗
本题要求从左上角走到右下角，并且还会有强制消费，因此我们根据状态**递推**。为了保证最优解，我们是可以不理会它的强制消费转而向左或向上走，但是这样可能会有**时间不同步**的情况，不方便处理，所以我们试着把这个过程**分层**。类似广搜，实则**DP**，我们每次**只走一步**更新状态是最稳妥的。而对于每个状态取的都是**最小值**，所以引出了**DP**的思想。
对于每个点来说，我们一旦出发,**时间轴**就会向前推进，为了保证状态正确，我们额外开一维使得状态只能来**自同时的相邻的四个点**，也就是**分层**的思想。那么一直推下去，理论最坏复杂度为$N^5$，路径长度可能达到$N^2$甚至更多，而根据考试策略，对于最大情况100×100控制在1s以内（最好是0.8s左右），来控制分层图的层数。于是我就定了分层为一个**固定的不会爆1s**的常数~~（经测试33333可能比较符合我的常数）~~除以n的大小，这样既保证了小数据的正确性（此时n较小），又可以碰碰运气看较大数据是否能跑出正确解。
这个题还是有一些细节需要注意的，不仅是判断加油或绕路，而且还可以在**任何想建立**加油站的地方建立加油站，然后更新每个状态取最小值就可以了，只要**方程中**状态相同，从这里怎么转移出去都是一样的，就有点像**DP**的做法了。
实际上，由于最短路径长度为2n-1，加油费用与向上/左绕路在变动较大时可能是**加油更优**，那么我们基本可以推测到最短路径的长度在4n以内（虽然题目没给A,B,C的范围），考试时为了稳妥还是稍微卡一下时好了。转移方程也是比较清晰的~~，就是状态比较多**而已**~~。
## Code：
```cpp
#include<cstdio>
#include<cstring>
int min(int x,int y)
{
return x<y?x:y;
}
int f[2][105][105][12];//第一维滚动 二三维坐标 第四维是还剩多少油
int g[105][105];
int ans=0x7fffffff;
int main()
{
memset(f,0x3f,sizeof(f));
int n,k,a,b,c;
scanf("%d%d%d%d%d",&n,&k,&a,&b,&c);
f[0][1][1][k]=0;//初始化
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&g[i][j]);
int up=33333/n;
for(int t=1;t<=up;t++)//这是一个不爆时间的范围
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
if(g[i][j]==0)//没有强制消费
{
for(int l=1;l<=k;l++)
{
f[t&1][i][j][l-1]=0x3f3f3f3f;//滚动数组优化时间（也可以不用这一行，因为越到后面越费钱）
if(i>1)
f[t&1][i][j][l-1]=min(f[t&1][i][j][l-1],f[t&1^1][i-1][j][l]);
if(i<n)
f[t&1][i][j][l-1]=min(f[t&1][i][j][l-1],f[t&1^1][i+1][j][l]+b);
if(j>1)
f[t&1][i][j][l-1]=min(f[t&1][i][j][l-1],f[t&1^1][i][j-1][l]);
if(j<n)
f[t&1][i][j][l-1]=min(f[t&1][i][j][l-1],f[t&1^1][i][j+1][l]+b);
if(i==j&&j==n)//更新答案
ans=ans<f[t&1][i][j][l-1]?ans:f[t&1][i][j][l-1];
}
if(i>1)
f[t&1][i][j][k]=min(f[t&1][i][j][k],f[t&1^1][i-1][j][1]+c+a);
if(i<n)
f[t&1][i][j][k]=min(f[t&1][i][j][k],f[t&1^1][i+1][j][1]+c+a+b);
if(j>1)
f[t&1][i][j][k]=min(f[t&1][i][j][k],f[t&1^1][i][j-1][1]+c+a);
if(j<n)
f[t&1][i][j][k]=min(f[t&1][i][j][k],f[t&1^1][i][j+1][1]+c+a+b);
if(i==j&&j==n)
ans=ans<f[t&1][i][j][k]?ans:f[t&1][i][j][k];
}
else//有强制消费
{
for(int l=1;l<=k;l++)
{
if(i>1)
f[t&1][i][j][k]=min(f[t&1][i][j][k],f[t&1^1][i-1][j][l]+a);
if(i<n)
f[t&1][i][j][k]=min(f[t&1][i][j][k],f[t&1^1][i+1][j][l]+a+b);
if(j>1)
f[t&1][i][j][k]=min(f[t&1][i][j][k],f[t&1^1][i][j-1][l]+a);
if(j<n)
f[t&1][i][j][k]=min(f[t&1][i][j][k],f[t&1^1][i][j+1][l]+a+b);
}
}
}
printf("%d\n",ans);
return 0;
}
```