P1043 数字游戏【洛谷算法习题】

P1043 数字游戏网页链接P1043 数字游戏题目描述丁丁最近沉迷于一个数字游戏之中。这个游戏看似简单但丁丁在研究了许多天之后却发觉原来在简单的规则下想要赢得这个游戏并不那么容易。游戏是这样的在你面前有一圈整数一共n nn个你要按顺序将其分为m mm个部分各部分内的数字相加相加所得的m mm个结果对10 1010取模后再相乘最终得到一个数k kk。游戏的要求是使你所得的k kk最大或者最小。例如对于下面这圈数字n 4 n4n4m 2 m2m2要求最小值时( ( 2 − 1 ) m o d 10 ) × ( ( 4 3 ) m o d 10 ) 1 × 7 7 ((2-1)\bmod10)\times ((43)\bmod10)1\times 77((2−1)mod10)×((43)mod10)1×77要求最大值时为( ( 2 4 3 ) m o d 10 ) × ( − 1 m o d 10 ) 9 × 9 81 ((243)\bmod10)\times (-1\bmod10)9\times 981((243)mod10)×(−1mod10)9×981。特别值得注意的是无论是负数还是正数对10 1010取模的结果均为非负值。丁丁请你编写程序帮他赢得这个游戏。输入格式输入文件第一行有两个整数n nn1 ≤ n ≤ 50 1\le n\le 501≤n≤50和m mm1 ≤ m ≤ 9 1\le m\le 91≤m≤9。以下n nn行每行有个整数其绝对值≤ 10 4 \le10^4≤104按顺序给出圈中的数字首尾相接。输出格式输出文件有2 22行各包含1 11个非负整数。第1 11行是按题目要求对10 1010取模后得到的最小值第2 22行是按题目要求对10 1010取模后得到的最大值。输入输出样例 #1输入 #14 2 4 3 -1 2输出 #17 81说明/提示【题目来源】NOIP 2003 普及组第二题解题思路本题是环形区间动态规划的经典问题。给定一个环形排列的n nn个整数需要按顺序将其分成m mm个连续部分每部分求和后对10 1010取模结果非负再将这些模值相乘分别求乘积的最小值和最大值。1. 问题等价转化环形处理由于是环需要枚举所有可能的断点将环断成链。代码中外层循环l 0 ∼ n − 1 l 0 \sim n-1l0∼n−1表示从第l 1 l1l1个元素开始作为链的起点。非负取模题目要求无论正负对10 1010取模的结果均为非负。因此计算时使用(x 10000) % 10保证结果在[ 0 , 9 ] [0, 9][0,9]范围内10000 1000010000是10 1010的倍数足够大以消除负数。状态定义dmax[k][i]将前i ii个数分成k kk部分各部分模值乘积的最大值。dmin[k][i]同理乘积的最小值。前缀和sum[i]表示从断点开始的链上前i ii个数的累加和模10 1010非负。2. 状态转移初始化dmin[1][i] dmax[1][i] sum[i]即前i ii个数作为一整段时的模值。转移方程对于k ≥ 2 k \ge 2k≥2枚举最后一段的起点j jj1 ≤ j i 1 \le j i1≤jidmax [ k ] [ i ] max ⁡ j ( dmax [ k − 1 ] [ j ] × seg ( j 1 , i ) ) \text{dmax}[k][i] \max_{j} \left( \text{dmax}[k-1][j] \times \text{seg}(j1, i) \right)dmax[k][i]jmax​(dmax[k−1][j]×seg(j1,i))dmin [ k ] [ i ] min ⁡ j ( dmin [ k − 1 ] [ j ] × seg ( j 1 , i ) ) \text{dmin}[k][i] \min_{j} \left( \text{dmin}[k-1][j] \times \text{seg}(j1, i) \right)dmin[k][i]jmin​(dmin[k−1][j]×seg(j1,i))其中seg ( j 1 , i ) ( sum [ i ] − sum [ j ] 10000 ) % 10 \text{seg}(j1, i) (\text{sum}[i] - \text{sum}[j] 10000) \% 10seg(j1,i)(sum[i]−sum[j]10000)%10表示第j 1 j1j1到i ii个数的和模10 1010。循环范围i ii从1 11到n − m k n-mkn−mk确保有足够的位置放置k kk段。3. 统计答案对于每个断点l ll计算dmax[m][n]和dmin[m][n]。全局最大值ans和最小值anss分别更新。最终输出anss最小值和ans最大值。4. 复杂度分析时间复杂度外层枚举断点O ( n ) O(n)O(n)内层 DP 状态数O ( m ⋅ n ) O(m \cdot n)O(m⋅n)转移O ( n ) O(n)O(n)总复杂度O ( n 2 ⋅ m ⋅ n ) O ( n 3 m ) O(n^2 \cdot m \cdot n) O(n^3 m)O(n2⋅m⋅n)O(n3m)。n ≤ 50 , m ≤ 9 n \le 50, m \le 9n≤50,m≤9运算量约10 6 10^6106非常快。空间复杂度DP 数组O ( m ⋅ n ) O(m \cdot n)O(m⋅n)前缀和O ( n ) O(n)O(n)。总结通过枚举所有断点将环形问题转化为链形问题利用区间 DP 分别计算最小和最大乘积。关键在于正确处理非负取模以及状态转移时枚举最后一段的起点。方法直观高效适合小规模数据。代码简要说明全局数组dmax[15][N]、dmin[15][N]存储 DP 状态sum[N]为前缀和a[N]存储输入。外层循环l枚举环的断点从第l 1 l1l1个元素开始构造链。前缀和计算sum[i] (sum[i-1] a[(il-1)%n1] 10000) % 10保证非负。DP 初始化dmin[1][i] dmax[1][i] sum[i]。DP 转移三重循环枚举段数k kk、终点i ii、分割点j jj更新最大最小值。答案更新每个断点计算完后更新全局ans和anss。输出第一行最小值第二行最大值。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N55;constll INF1e18;constll M1e610;constll mod1e97;ll n,m;ll dmax[15][N],dmin[15][N];ll sum[N],a[N],ans,anss1e9;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cinnm;for(ll i1;in;i)cina[i];for(ll l0;ln-1;l){memset(dmax,0,sizeofdmax);memset(dmin,0,sizeofdmin);sum[0]0;for(ll i1;in;i){sum[i](sum[i-1]a[(il-1)%n1]10000)%10;dmin[1][i]sum[i];dmax[1][i]sum[i];}for(ll k2;km;k){for(ll i1;in-mk;i){dmin[k][i]1e9;for(ll j1;ji;j){if(dmin[k-1][j]1e9){dmax[k][i]max(dmax[k][i],dmax[k-1][j]*((sum[i]-sum[j]10000)%10));dmin[k][i]min(dmin[k][i],dmin[k-1][j]*((sum[i]-sum[j]10000)%10));}}}}ansmax(ans,dmax[m][n]);anssmin(anss,dmin[m][n]);}coutanssendlans;return0;}