题解：P17114 [Algo Beat 009 & MROI-R1] Payment

· · 题解

Section 0 闲篇

这是本蒟蒻的第一篇题解。

注意到我和题解一般是这个关系：会做的题不需要我写，需要我写的题又不太会做。（点个赞吧 ovo）

题目传送门

建议没读过题目的读者先阅读原题面。

Section 1 题目分析

小 L 今天一共坐了 n 段地铁，第 i 段原本需要支付 a_i 元。

由于系统延迟，每一段乘车费用不会立即结算，而是按照如下规则统一处理。你可以将连续的若干段地铁乘车记录划分为一组进行结算：

  • 当一组中只有 1 段乘车记录时，不触发任何优惠，需全额支付；
  • 当一组中包含的乘车段数 \ge 2 时，该组中费用最高的一段免费（若有多个最高费用，只免费其中一段）。

请你合理划分结算区间，使得小 L 最终需要支付的总费用最少。

结合题意可以提取出两个关键点：分组必须连续；每组至多免除一段费用。

注意到一个贪心结论：将连续段两两分组通常是最优的。

但问题在于我们发现输入规模并不一定为偶数。当 n 为奇数时，必然会有至少一个元素无法配对，只能单独成组。

赛时，像我这样聪明的人还讨论过“哪一个元素落单”“落单元素是否只能在奇数位”等问题，结果越分越复杂，甚至多次把自己 hack 掉。所以最终放弃了这种繁琐的分类讨论——即便讨论出来，实现难度也会非常高。

Section 2 正确思路

我们保留“两两分组较优”的直觉，在此基础上进一步思考。观察数据范围：

本题采用捆绑测试。

对于所有数据，满足：

注意：由于本题输入量较大，请关闭同步流或使用快速读入、scanf 等方式完成输入。

看到 n 高达 8 \times 10^6，大的离谱到我都没见过这么这么大数据，不过基本可以让我们可以确定：本题需要 \mathcal{O}(n) 的线性算法。

在线性约束下，一个自然的想法是使用 DP。类比 01 背包的思想，我们考虑每个元素是“单独结算”“与左侧配对”还是“与右侧配对”，共三种状态。

以样例 1 为例，手动模拟如下：

for(int i=1; i<=n; i++){
    dp[i][0]=dp[i-1][2]+min(a[i-1],a[i]);
    //状态0 结算上一个状态2
    dp[i][1]=min(dp[i-1][0],dp[i-1][1])+a[i];
    //状态1 选择上一个中已闭合的答案的最优答案
    dp[i][2]=min(dp[i-1][0],dp[i-1][1]);
    //状态2 继承最优答案
}
dp[n][2]+=a[n];
//单独结算最后一次 这很重要
long long MIN=min(dp[n][0],min(dp[n][1],dp[n][2]));
//……

Section 3 完整代码

以下为赛时 AC 代码。为了可读性和美观，对快读模板进行了格式化整理。

#include<iostream>
#include<cstdio>
#define n_max (int)(8e6+1)
using namespace std;
inline int read() {
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
      if(ch=='-') f=-1;
      ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
      x=x*10+ch-'0';
      ch=getchar();
    }
    return x*f;
}
int n;
int a[n_max];
long long dp[n_max][3];
int main(){
    n=read();
    for(int i=1; i<=n; i++) a[i]=read();
    a[0]=(int)(1e9+1);
    for(int i=1; i<=n; i++){
        dp[i][0]=dp[i-1][2]+min(a[i-1],a[i]);
        dp[i][1]=min(dp[i-1][0],dp[i-1][1])+a[i];
        dp[i][2]=min(dp[i-1][0],dp[i-1][1]);
    }
    dp[n][2]+=a[n];
    long long MIN=min(dp[n][0],min(dp[n][1],dp[n][2]));
    printf("%lld",MIN);
    return 0;
}

Section 4 注意事项

最后提醒几个容易出错的点：

祝各位顺利 AC 本题！