新闻详情

新闻详情

首页 / 资讯中心 / 详情

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

发布时间:2026/11/16 15:48:06来源:尧图网络
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;}
网站建设高端定制企业官网
RELATED

相关资讯

更多精彩内容,欢迎继续阅读

较早相关资讯

最新相关资讯

【外设】之大彩串口显示屏 2026/11/15 4:54:16

【外设】之大彩串口显示屏

大彩串口屏初步使用 1 .官网下载 STM32 屏幕 GUI 设计资料 http://www.gz-dc.com/category/typeid/4112 找到 STM32 Keil 工程,移植相关代码因项目而异进行移植,由于项目简单,本人只对用到的指令接口进行修改。 比如:注意事项&…

阅读更多 →
无法下载Windows系统iso文件 2026/11/15 2:04:12

无法下载Windows系统iso文件

当我遇到这个问题的时候,我打开了一个网站: 登录 然后我打算下载的时候: 突然那个官方的连接就可以下载了:

阅读更多 →
【清华代码熊】DeepSeek V4.1 Flash 后训练详解 2026/11/14 10:11:15

【清华代码熊】DeepSeek V4.1 Flash 后训练详解

📌 上期解析了 DeepSeek V4.1 Flash 模型架构改进,本期解析 DeepSeek V4.1 Flash 预训练/后训练技术: 🌟 预训练:45T 文本 多模态混合语料、直接训练 sparse attention(取消 DeepSeek V4 的 dense 冷启动&…

阅读更多 →
Shuffle-R1: Efficient RL framework for Multimodal Large Language Models via Data-centric Dynamic ... 2026/11/16 6:47:19

Shuffle-R1: Efficient RL framework for Multimodal Large Language Models via Data-centric Dynamic ...

文章主要内容和创新点 主要内容 本文聚焦于多模态大语言模型(MLLM)强化学习(RL)训练中的效率问题,提出了一个名为Shuffle-R1的框架。研究发现,当前RL训练存在两个关键缺陷: 优势值坍缩(Advantage Collapsing):批次中大多数优势值集中在零附近,导致有效梯度信号被淹…

阅读更多 →
PRvL: Quantifying the Capabilities and Risks of Large Language Models for PII Redaction 2026/11/14 16:35:50

PRvL: Quantifying the Capabilities and Risks of Large Language Models for PII Redaction

一、文章主要内容总结 本文聚焦于利用大型语言模型(LLMs)实现个人身份信息(PII)脱敏的研究,旨在解决传统脱敏方法(如基于规则的系统、领域特定命名实体识别(NER)模型)泛化能力差、跨格式/跨语境适应性弱的问题。 研究通过全面评估多种LLM架构(包括密集型LLM(D-LLM…

阅读更多 →
LLaVA-RE: Binary Image-Text Relevancy Evaluation with Multimodal Large Language Model 2026/11/15 4:06:36

LLaVA-RE: Binary Image-Text Relevancy Evaluation with Multimodal Large Language Model

文章主要内容和创新点 主要内容 本文聚焦于二进制图像-文本相关性评估任务(判断图像与文本“相关”或“不相关”),针对该任务中文本格式多样、相关性定义随场景变化等挑战,提出了基于多模态大语言模型(MLLM)的解决方案LLaVA-RE。 模型设计:LLaVA-RE基于LLaVA 1.5架构,…

阅读更多 →

今日资讯

本周资讯

本月资讯

看完文章仍有疑问?

联系尧图顾问,获取一对一建站咨询

立即免费咨询 📞 400-888-8888
📞 ✉