P15919 [TOPC 2023] Cutting into Monotone Increasing Sequence 题解

P15919 [TOPC 2023] Cutting into Monotone Increasing SequenceLink: https://www.luogu.com.cn/problem/P15919题目描述单调序列是指随着序列的推进数值始终一致地增加或一致地减少的序列。换句话说它表现出向上或向下的稳定趋势。在单调递增序列中序列中的每一项都大于或等于前一项。数学上对于序列a 1 , … , a n a_1, \dots, a_na1​,…,an​它是单调递增的当且仅当对于每个1 ≤ i n 1 \le i n1≤in有a i ≤ a i 1 a_i \le a_{i1}ai​≤ai1​。例如序列1 , 2 , 2 , 4 , 5 1, 2, 2, 4, 51,2,2,4,5是单调递增序列因为每一项都大于或等于前一项。单调序列在数学的各个领域包括微积分和分析中都很重要因为它们通常能简化函数及其行为分析。它们提供了一种清晰且一致的趋势使人们更容易理解序列或函数在数值范围内的行为。我们的一位命题者非常喜欢大整数。在过去几年中台湾线上程式设计竞赛经常出现涉及大整数的题目。这一次我们有一个将大整数与单调递增序列结合起来的问题。你的任务是通过在数字之间的空隙中插入逗号,将一个大整数x xx转换为一个单调递增序列同时遵守以下约束该单调递增序列的最后一项不超过b bb。逗号不能插入在数字0 00之前。逗号的数量最少。假设x xx是一个有k kk位的整数表示为d 1 d 2 ⋯ d k d_1 d_2 \cdots d_kd1​d2​⋯dk​。例如如果x 654321 d 1 d 2 ⋯ d 6 x 654321 d_1 d_2 \cdots d_6x654321d1​d2​⋯d6​且b 1000 b 1000b1000我们可以在d 3 d_3d3​之后和d 5 d_5d5​之后插入逗号将x xx转换为以下单调递增序列6 , 54 , 321 6, 54, 3216,54,321。请编写一个程序计算将给定的大整数x xx转换为由不超过给定整数b bb的数组成的单调递增序列所需的最少逗号数。如果无法转换请输出NO WAY。输入格式输入包含两个非负整数x xx和b bb。输出格式输出将x xx转换为由不超过b bb的数组成的单调递增序列所需的最少逗号数。如果无法转换请输出NO WAY。输入输出样例 #1输入 #1654321 1000输出 #12输入输出样例 #2输入 #2654321 100输出 #2NO WAY说明/提示x ≤ 10 100000 x \le 10^{100000}x≤10100000b 2 64 b 2^{64}b264如果x 0 x 0x0则没有前导零。Solution1. 题意用逗号分隔一个长数字串x xx要求分隔产生的每个整数从前往后单调递增且不能超过给定的上限b bb最小化逗号的数量。2. 分析这是一道典型的动态规划问题。注意到b ≤ 2 64 ≈ 1.84 × 10 19 b \le 2^{64} ≈ 1.84 \times 10^{19}b≤264≈1.84×1019这也就意味着划分出来的每一段均不会超过20 2020个数字因此从贪心的角度讲也就意味着要尽可能最大化数字的长度。2.0 符号说明将大整数视为字符串s ss参考 C# 8.0 以及 Python 的切片机制为简明起见我们用记号s ( i , j ) \color{blue}s(i,j)s(i,j)表示字符串s ss的下标i ∼ j i\sim ji∼j的一段对标 C# 的..运算符用记号v ( i , j ) \color{blue}v(i,j)v(i,j)表示s ss对应的十进制值对标 C# 的Convert.ToInt64或者 C 的stoi之类的方法。2.1 dp 模型 还有符号说明考虑到本题同时要考虑当前的数值以及当前最优的逗号插入次数因此动态规划使用的数组需要同时维护这两者。设数组dp[i]的每个元素皆为二元组(min_cnt, max_val)存储的是s ( i , k − 1 ) s(i,k-1)s(i,k−1)的最优拆分方案。其中前者表示分割成合法单增数字序列所需的最少次数即dp[i].min_cnt记为{ C i } \color{blue}\{C_i\}{Ci​}后者表示在这个次数最好的前提下已被拆分的序列的第一项s ( i , j − 1 ) s(i,j-1)s(i,j−1)再往前的需要在数值上严格小于此值对应的v ( i , j − 1 ) v(i,j-1)v(i,j−1)的最大可能值即dp[i].max_val记为{ V i } \color{blue}\{V_i\}{Vi​}。其中最大化v ( i , j − 1 ) v(i,j-1)v(i,j−1)的目的是尽可能为靠前的序列提供更大的取值范围和更宽的小于等于约束。2.2 状态转移状态转移的核心思路是对于位置i ii在20 2020以内的范围内枚举下一段的长度δ \deltaδ并调取这一段的数值v ( i , i δ − 1 ) v(i, i\delta-1)v(i,iδ−1)。若v ( i , i δ − 1 ) b v(i, i\delta - 1) bv(i,iδ−1)b意味着超限了方案不可行提前结束若v ( i , i δ − 1 ) ≤ b v(i, i\delta - 1) \le bv(i,iδ−1)≤b的同时亦有v ( i , i δ − 1 ) ≤ V i δ v(i, i \delta - 1) \le V_{i\delta}v(i,iδ−1)≤Viδ​说明当前段可以接在最优后缀之前满足单调性。此时候选段数为C i δ 1 C_{i\delta} 1Ciδ​1。按照上面两条原则不断更新dp[i]优先最小化段数C CC段数已被最小化的情况下最大化V VV即可。2.3 边界条件 预处理初始化时将所有的C i C_iCi​全部置零所有的V i V_iVi​全部置最大值作为边界条件。由于题目要求“逗号不能插入在数字0 00之前”即除整个字符串开头外任何段的开头不能带前导0 00。因此若i 0 i0i0且s ( i , i ) 0 s(i,i) \texttt{0}s(i,i)0直接跳过该位置。最终的答案就是C 0 − 1 C_0-1C0​−1逗号数 段数− 1 -1−1。若C 0 ∞ C_0 \inftyC0​∞意味着无解输出NO WAY。2.4 时间复杂度作为经典的一维 dp本题的时间复杂度为O ( n ) O(n)O(n)且带有常数20 2020。3. 代码usingSystem;usingSystem.Numerics;classP15919{staticvoidMain(){varinputConsole.ReadLine().Split();stringsinput[0];if(snull)return;stringbStrinput[1];if(bStrnull)return;if(!ulong.TryParse(bStr,outulongb))return;intks.Length;constintINF(int)1e9;// dp[i].Item1 : minimum number of segments for suffix s[i...k-1]// dp[i].Item2 : maximum value of the first segment when the number of segments is minimalvardpnew(int,ulong)[k1];for(inti0;ik;i)dp[i](INF,0);dp[k](0,ulong.MaxValue);for(intik-1;i0;--i){// Constraint: no segment can start with 0 unless its the entire numberif(i0s[i]0)continue;ulongv0;for(intlen1;len20ilenk;len){intds[ilen-1]-0;// Check if v * 10 d b safelyif(vb/10||(vb/10(ulong)db%10))break;vv*10(ulong)d;if(dp[ilen].Item1INF)continue;if(vdp[ilen].Item2){intcntdp[ilen].Item11;if(cntdp[i].Item1||(cntdp[i].Item1vdp[i].Item2)){dp[i](cnt,v);}}}}if(dp[0].Item1INF){Console.WriteLine(NO WAY);}else{Console.WriteLine(dp[0].Item1-1);}}}