Csp-j 2023 T2题解

· · 题解

Csp-j 2023 T2题解

该题解中各个变量/名词含义

为表示方便，该题解会使用 minprice_i 来代表前 i 个站点中油价最低的站点的油价，“区间 i”来代表第 i-1 个站点到第 i 个站点，v_i 来代表区间 i 的距离（注意与题中意思不同），f_i 来代表通过第一个站点到第 i 个站点需要花费的最少钱，其他变量的意思与题中所述意思一样。具体见下图：

使用什么算法

这道题使用动态规划算法做比较简单。因为我们在题目中会发现一个规律：通过第 1 个站点到第 i 个站点需要的最小花费等于通过第 1 个站点到第 i-1 个站点的最小花费加上通过区间 i 需要的最小花费。 这就可以联想到动态规划。

算法步骤

  1. 拆分问题

这很简单，在“使用什么算法”板块我就说了，第一个站点到第 i 个站点的最小花费等于第一个站点到第 i-1个站点的最小花费加上第 i-1 个站点到第 i 个站点的最小花费。

  1. 推导状态转移方程

我接下来会使用 minprice_i 来代表前 i 个站点中油价最低的站点的油价，“区间 i”或“区间 i-1 到 i”来代表第 (i-1) 个站点到第 i 个站点，v_i 来代表区间 i 的距离（注意与题中意思不同），f_i 来代表经过“区间 1 到 i”需要花费的最少钱（状态数组），其他变量与题中所述意思一样。

则通过区间 i 需要买的最少油量（以后用 buyyou 表示）为：

buyyou = \operatorname{ceil}(v_i \div d)

由上面“拆分问题”步骤，可以得到状态转移方程为 f_i = f_{i-1} + 通过区间 i 需要的最小花费。但这个“通过区间 i 需要的最小花费”该怎么表示呢？很显然，它表示为“buyyou \times minprice_{i-1}”。因为通过区间 i 需要买 buyyou 升油，这几升油在前面随便哪个加油站加都可以，而前面加油站中最便宜的油价为 minprice_{i-1}，所以我们以这个油价买下 buyyou升油，就是最小花费了。完整状态转移方程：

f_i = f_{i-1} + buyyou \times minprice_{i-1}
  1. 确定边界
4. 具体实现 在这一步本来应该写代码了，但是还有一种我们未处理的情况。 这种情况就是多买。你可能注意到了我在计算 $buyyou$ 时使用 $\operatorname{ceil}()$ 向上取整。这是因为：虽然题目中并没有说必须买整数升的油，但是根据样例，我们只能买整数升的油。所以 $buyyou$ 必须为整数，也就是经过区间 $i$ 如果只需要买小数升油，则必须多买一些油凑整。那么，多买的油可行驶路程（**以后用 $duobuylc$ 表示**）为： $duobuylc= buyyou \times d - v_i

因为我们买的油可行驶路程为 buyyou \times d，而我们需要在区间 i 的行驶路程仅仅为 v_i。

把后面的路程减去 duobuylc，多买这种情况就处理完了。对于每个 v_i，该操作的代码如下：

int j;
for(j=i+1;j<=n&&v[j]<duobuylc;j++)
{
    //当第j段路程v[j]<duobuylc时，把它归零，并把duobuylc减去v[j]。直到v[j]>=duobuylc或j>n
    duobuylc-=v[j];
    v[j]=0;
}
if(j<=n)v[j]-=duobuylc;

除了多买，就没有特殊情况了，上代码：

#include <cstdio>
#include <cstdlib>
#include <queue>
#include <cstring>
#include <cmath>
using namespace std;
int n,d,p[100001],v[100001],minprice[100001];
long long f[100001];//f最后会超过int表示范围，所以使用long long类型。 
int main()
{
//  freopen("road.in","r",stdin);
//  freopen("road.out","w",stdout);
    memset(minprice,0x3f,sizeof(minprice));
    scanf("%d%d",&n,&d);
    v[1]=0;
    for(int i=2;i<=n;i++)
        scanf("%d",&v[i]);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&p[i]);
        minprice[i]=min(minprice[i-1],p[i]);//钱i个站点的最便宜油价
    }
    f[1]=0;
    for(int i=2;i<=n;i++)
    {
        int buyyou=ceil(v[i]/double(d)),duobuylc=buyyou*d-v[i];
     //buyyou:需要买的油数量，duobuylc：多买的油可行驶路程
        f[i]=f[i-1]+buyyou*minprice[i-1];
     //状态转移方程

        int j;
        for(j=i+1;j<=n&&v[j]<duobuylc;j++)
        {
            duobuylc-=v[j];
            v[j]=0;
        }
        if(j<=n)v[j]-=duobuylc;
      //把后面的路程减去多买油可以行驶的路程
    }
    printf("%ld",f[n]);
    return 0;
}