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

作者: wjyyy 分类: DP,分层图,枚举,滚动数组,解题报告 发布时间: 2018-07-05 16:07

点击量:79

 

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

题目描述

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

233

一辆汽车从起点◎出发驶向右下角终点▲,其坐标为(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;
}

 

 

说点什么

avatar
  Subscribe  
提醒
/* */