洛谷 P4009 汽车加油行驶问题 题解【DP】【枚举】【分层图】

点击量：329

网络流24题里比较水的一道？？

目录

题目描述

给定一个N×N的方形网格，设其左上角为起点◎，坐标为(1,1)，X轴向右为正，Y轴向下为正，每个方格边长为1，如图所示。

一辆汽车从起点◎出发驶向右下角终点▲，其坐标为(N,N)。

在若干个网格交叉点处，设置了油库，可供汽车在行驶途中加油。汽车在行驶过程中应遵守如下规则:

1. 汽车只能沿网格边行驶，装满油后能行驶K条网格边。出发时汽车已装满油，在起点与终点处不设油库。
2. 汽车经过一条网格边时，若其X坐标或Y坐标减小，则应付费用B，否则免付费用。
3. 汽车在行驶过程中遇油库则应加满油并付加油费用A。
4. 在需要时可在网格点处增设油库，并付增设油库费用C (不含加油费用A )。
5. N,K,A,B,C均为正整数， 且满足约束: 2≤N≤100,2≤K≤10 。

设计一个算法，求出汽车从起点出发到达终点所付的最小费用。

输入输出格式

输入格式：

文件的第一行是N,K,A,B,C的值。

 

第二行起是一个N×N的0−1方阵,每行N个值,至N+1行结束。

 

方阵的第i行第j列处的值为1表示在网格交叉点(i,j)处设置了一个油库,为0时表示未设油库。各行相邻两个数以空格分隔。

 

输出格式：

程序运行结束时,输出最小费用。

输入输出样例

输入样例#1：

9 3 2 3 6

0 0 0 0 1 0 0 0 0

0 0 0 1 0 1 1 0 0

1 0 1 0 0 0 0 1 0

0 0 0 0 0 1 0 0 1

1 0 0 1 0 0 1 0 0

0 1 0 0 0 0 0 1 0

0 0 0 0 1 0 0 0 1

1 0 0 1 0 0 0 1 0

0 1 0 0 0 0 0 0 0

输出样例#1：

12

题解

   本题要求从左上角走到右下角，并且还会有强制消费，因此我们根据状态递推。为了保证最优解，我们是可以不理会它的强制消费转而向左或向上走，但是这样可能会有时间不同步的情况，不方便处理，所以我们试着把这个过程分层。类似广搜，实则DP，我们每次只走一步更新状态是最稳妥的。而对于每个状态取的都是最小值，所以引出了DP的思想。

   对于每个点来说，我们一旦出发,时间轴就会向前推进，为了保证状态正确，我们额外开一维使得状态只能来自同时的相邻的四个点，也就是分层的思想。那么一直推下去，理论最坏复杂度为$ N^5$，路径长度可能达到$ N^2$甚至更多，而根据考试策略，对于最大情况100×100控制在1s以内（最好是0.8s左右），来控制分层图的层数。于是我就定了分层为一个固定的不会爆1s的常数除以n的大小，这样既保证了小数据的正确性（此时n较小），又可以碰碰运气看较大数据是否能跑出正确解。

   这个题还是有一些细节需要注意的，不仅是判断加油或绕路，而且还可以在任何想建立加油站的地方建立加油站，然后更新每个状态取最小值就可以了，只要方程中状态相同，从这里怎么转移出去都是一样的，就有点像DP的做法了。

   实际上，由于最短路径长度为2n-1，加油费用与向上/左绕路在变动较大时可能是加油更优，那么我们基本可以推测到最短路径的长度在4n以内（虽然题目没给A,B,C的范围），考试时为了稳妥还是稍微卡一下时好了。转移方程也是比较清晰的，就是状态比较多而已。

Code：

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