题解：AtCoder AT_awc0098_c Highway Discount Pass

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

AtCoder：C - Highway Discount Pass

【题目描述】

Takahashi is about to drive along a long highway. This highway hasN NNtoll gates lined up in a row, numbered from1 11toN NN, and each toll gatei iiis assigned an identification code consisting of a single lowercase alphabet letter. When the identification codes of theN NNtoll gates are arranged in order of their numbers, a stringS SSof lengthN NNis obtained. That is, thei ii-th character ofS SSis the identification code of toll gatei ii.

Takahashi must pass through all toll gates from toll gate1 11to toll gateN NNin ascending order of their numbers. Normally, passing through each toll gate takes a travel time of1 11, so without any optimization, the total travel time isN NN.

However, Takahashi has a discount pass. The discount pass is represented by a stringT TTof lengthM MM. By using this discount pass, it may be possible to pass through exactlyM MMconsecutive toll gates together with a travel time of1 11. The discount pass can be used any number of times, but the intervals to which it is applied must not overlap.

Specifically, the conditions for applying the discount pass are as follows. For an interval consisting ofM MMconsecutive toll gates, namely toll gatesl , l + 1 , … , l + M − 1 l, l+1, \ldots, l+M-1l,l+1,…,l+M−1(1 ≤ l ≤ N − M + 1 1 \leq l \leq N-M+11≤l≤N−M+1), if the string formed by arranging their identification codes in order (the substring ofS SSfrom thel ll-th character to the( l + M − 1 ) (l+M-1)(l+M−1)-th character) matchesT TT, then the discount pass can be applied to that interval. When applied, thoseM MMtoll gates can be passed together with a travel time of1 11(instead of the usual travel time ofM MM).

Takahashi can choose0 00or more intervals to apply the discount pass, but no two chosen intervals may share a common toll gate. It is fine for the last toll gate of one interval and the first toll gate of another interval to have consecutive numbers (i.e., be adjacent).

Toll gates not included in any interval where the discount pass is applied are passed individually, each taking a travel time of1 11. If the number of intervals where the discount pass is applied isk kk, the total travel time isk + ( N − k M ) = N − k ( M − 1 ) k + (N - kM) = N - k(M - 1)k+(N−kM)=N−k(M−1).

Find the minimum total travel time for Takahashi to pass through all toll gates.

高橋即将驾车行驶一条长高速公路。这条高速公路上有N NN个收费站排成一排，编号从1 11到N NN，每个收费站i ii被分配了一个由单个小写英文字母组成的识别码。当将N NN个收费站的识别码按编号顺序排列时，得到一个长度为N NN的字符串S SS。也就是说，S SS的第i ii个字符是收费站i ii的识别码。

高橋必须按编号升序从收费站1 11通过到收费站N NN。正常情况下，通过每个收费站需要1 11的通行时间，因此没有任何优化时，总通行时间为N NN。

然而，高橋有一张折扣通行证。该折扣通行证由长度为M MM的字符串T TT表示。通过使用这张折扣通行证，可能可以将恰好M MM个连续的收费站一起通过，且通行时间仅为1 11。折扣通行证可以使用任意多次，但应用的区间不能重叠。

具体地，应用折扣通行证的条件如下。对于由M MM个连续收费站组成的区间，即收费站l , l + 1 , … , l + M − 1 l, l+1, \ldots, l+M-1l,l+1,…,l+M−1（1 ≤ l ≤ N − M + 1 1 \leq l \leq N-M+11≤l≤N−M+1），如果按顺序排列它们的识别码所形成的字符串（即S SS从第l ll个字符到第( l + M − 1 ) (l+M-1)(l+M−1)个字符的子串）与T TT匹配，则可以将折扣通行证应用于该区间。应用时，这M MM个收费站可以一起通过，通行时间为1 11（而不是通常的通行时间M MM）。

高橋可以选择0 00个或多个区间应用折扣通行证，但任意两个选中的区间不能共享同一个收费站。一个区间的最后一个收费站与另一个区间的第一个收费站编号连续（即相邻）是允许的。

未被包含在任何折扣通行证应用区间中的收费站需逐个通过，每个通行时间为1 11。如果应用折扣通行证的区间数量为k kk，则总通行时间为k + ( N − k M ) = N − k ( M − 1 ) k + (N - kM) = N - k(M - 1)k+(N−kM)=N−k(M−1)。

求高橋通过所有收费站的最小总通行时间。

【输入】

N NNM MM
S SS
T TT

• The first line contains an integerN NNrepresenting the number of toll gates and an integerM MMrepresenting the length of the discount pass, separated by a space.
• The second line contains a stringS SSof lengthN NN, which is the identification codes of the toll gates arranged in order of their numbers.
• The third line contains a stringT TTof lengthM MM, representing the discount pass.

【输出】

Output in one line the minimum total travel time for Takahashi to pass through all toll gates.

【输入样例】

8 3 abcxxabc abc

【输出样例】

4

【算法标签】

#KMP

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintN=1000005;// 最大字符串长度intn,m,cnt;// n: S串长度, m: T串长度, cnt: 选中的匹配区间数量chars[N],p[N];// s: 收费站识别码字符串（下标从1开始）, p: 折扣通行证字符串intne[N];// KMP的next数组（前缀函数），ne[i]表示p[1..i]的最长相等前后缀长度vector<int>matches;// 存储所有T在S中匹配的起始位置intmain(){cin>>n>>m;// 读入N和M// 读入S串（下标从1开始）for(inti=1;i<=n;i++)cin>>s[i];// 读入T串（下标从1开始）for(inti=1;i<=m;i++)cin>>p[i];// ========== KMP预处理：求T串的next数组 ==========// ne[i] = p[1..i] 的最长相等真前缀和真后缀的长度for(inti=2,j=0;i<=m;i++){while(j&&p[i]!=p[j+1])// 不匹配时，回退到next[j]j=ne[j];if(p[i]==p[j+1])// 匹配成功，j++j++;ne[i]=j;// 记录p[1..i]的最长相等前后缀长度}// ========== KMP匹配：在S中查找所有T的出现位置 ==========for(inti=1,j=0;i<=n;i++){while(j&&s[i]!=p[j+1])// 不匹配时，回退到next[j]j=ne[j];if(s[i]==p[j+1])// 匹配成功，j++j++;if(j==m)// 完整匹配了一个T{// 记录匹配起始位置：当前位置i减去T的长度再加1matches.push_back(i-m+1);j=ne[j];// 继续匹配，回退到next[j]（允许重叠匹配）}}// ========== 贪心选择不重叠的匹配区间（最大化区间数量） ==========// 策略：按起始位置排序，每次选择最早结束且不与上一个重叠的区间intlast=-1;// 上一个选中区间的结束位置for(intpos:matches){intend=pos+m-1;// 当前匹配区间的结束位置if(pos>last)// 当前区间起始位置在上一个区间结束之后（不重叠）{cnt++;// 选中该区间last=end;// 更新last为当前区间的结束位置}}// 输出最小总通行时间// 总时间 = N - cnt * (M - 1)// 解释：每个选中的区间节省 (M-1) 的时间（M个收费站一起通过只需1，而不是M）cout<<n-cnt*(m-1)<<endl;return0;}

【运行结果】

8 3 abcxxabc abc 4