Description & Range
丁丁最近沉迷于一个数字游戏之中。这个游戏看似简单,但丁丁在研究了许多天之后却发觉原来在简单的规则下想要赢得这个游戏并不那么容易。游戏是这样的,在你面前有一圈整数(一共n个),你要按顺序将其分为m个部分,各部分内的数字相加,相加所得的m个结果对10取模后再相乘,最终得到一个数k。游戏的要求是使你所得的k最大或者最小。
例如,对于下面这圈数字(n=4,m=2):
要求最小值时,((2-1) mod 10)×((4+3) mod 10)=1×7=7,要求最大值时,为((2+4+3) mod 10)×(-1 mod 10)=9×9=81。特别值得注意的是,无论是负数还是正数,对10取模的结果均为非负值。
丁丁请你编写程序帮他赢得这个游戏。
Input
第一行有两个整数,n(1≤n≤50)和m(1≤m≤9)。以下n行每行有个整数,其绝对值不大于 $10^4$ ,按顺序给出圈中的数字,首尾相接。
Output
有两行,各包含一个非负整数。第一行是你程序得到的最小值,第二行是最大值。
Solution
啊这道题好有水平=.=
第一眼看到这题以为是和石子合并一样水的题,但是蛮多细节要注意的(我也是看题解才知道)
定义 f[0/1][i][j][k] 表示左端点在 i,右端点在 j,分成了 k 个部分的最大/最小乘积
最开始做这题开了五层循环,内层枚举了一下断点和断点两侧分别分成了多少个部分...
后来(抄题解)发现了其实不用枚举两侧分成了多少个部分,因为这会被之前或之后的循环枚举到,打个比方:如果枚举到了左端点是 i,右端点是 j,断点是 k,左边分成了p 个部分,右边分成了 q 个部分。
先明确一下,在合并时,我们只是关注 k+1~j 的前缀和再乘上左边已经乘好的部分, 即 f[i][j][p+q]=max{f[i][j][p+q-1]*(qzh[j]-qzh[k])} 所以是不用管右边分成了几个部分的,直接假设右边分成了一个部分,然后用左边的区间去“吃”右边的区间就好。
Code
// By YoungNeal #include<cstdio> #include<iostream> using namespace std; int n,m; ]; ]; ][][][]; int mod(int x){ +)%; } signed main(){ scanf("%d%d",&n,&m); ;i<=n;i++) scanf("%d",&val[i]),val[i+n]=val[i]; ;i<=(n<<);i++) qzh[i]=qzh[i-]+val[i]; ;i<=(n<<);i++){ );j++) f[][i][j][]=f[][i][j][]=mod(qzh[j]-qzh[i-]); } /*愚蠢的五层循环
for(int len=2;len<=(n<<1);len++){ for(int i=1;i<=(n<<1);i++){ int j=i+len-1; if(j>(n<<1)) break; for(int p=i;p<=j;p++){ for(int k=1;k<=min(m,j-i+1);k++){ for(int q=1;q<k;q++){ if(q<=p-i+1&&k-q<=j-p) f[i][j][k]=max(f[i][j][k],f[i][p][q]+f[p+1][j][k-q]+(qzh[p]-qzh[i-1])*(qzh[j]-qzh[p])); } } } } }*/ ;i<=m;i++){ ;l<=(n<<);l++){ ;r<=l+n-;r++){ //f[l][r][i] f[][l][r][i]=0x3f3f3f3f; ;k<r;k++){ //k不能=r! f[][l][r][i]=max(f[][l][r][i],f[][l][k][i-]*mod(qzh[r]-qzh[k])); f[][l][r][i]=min(f[][l][r][i],f[][l][k][i-]*mod(qzh[r]-qzh[k])); } } } } ,minn=0x3f3f3f3f; ;i<=n;i++) maxn=max(maxn,f[][i][i+n-][m]),minn=min(minn,f[][i][i+n-][m]); printf("%d\n%d",minn,maxn); ; }
[Noip2003 PJ] 数字游戏的更多相关文章
-
cogs 983. [NOIP2003] 数字游戏
983. [NOIP2003] 数字游戏 ★☆ 输入文件:numgame.in 输出文件:numgame.out 简单对比时间限制:1 s 内存限制:128 MB 题目描述 丁丁最近沉 ...
-
C语言猜数字游戏
猜数字游戏,各式各样的实现方式,我这边提供一个实现方式,希望可以帮到新手. 老程序猿就不要看了,黑呵呵 源代码1 include stdio.h include stdlib.h include ti ...
-
不一样的猜数字游戏 — leetcode 375. Guess Number Higher or Lower II
好久没切 leetcode 的题了,静下心来切了道,这道题比较有意思,和大家分享下. 我把它叫做 "不一样的猜数字游戏",我们先来看看传统的猜数字游戏,Guess Number H ...
-
java 猜数字游戏
作用:猜数字游戏.随机产生1个数字(1~10),大了.小了或者成功后给出提示. 语言:java 工具:eclipse 作者:潇洒鸿图 时间:2016.11.10 >>>>> ...
-
【原创Android游戏】--猜数字游戏Version 0.1
想当年高中时经常和小伙伴在纸上或者黑板上或者学习机上玩猜数字的游戏,在当年那个手机等娱乐设备在我们那还不是很普遍的时候是很好的一个消遣的游戏,去年的时候便写了一个Android版的猜数字游戏,只是当时 ...
-
【原创Android游戏】--猜数字游戏V1.1 --数据存储,Intent,SimpleAdapter的学习与应用
--------------------------------------------------------------- V0.1版本 上次做完第一个版本后,发现还有一些漏洞,并且还有一些可以添 ...
-
NOIP2003pj数字游戏[环形DP]
题目描述 丁丁最近沉迷于一个数字游戏之中.这个游戏看似简单,但丁丁在研究了许多天之后却发觉原来在简单的规则下想要赢得这个游戏并不那么容易.游戏是这样的,在你面前有一圈整数(一共n个),你要按顺序将其分 ...
-
Codevs 1229 数字游戏
1229 数字游戏 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 白银 Silver 题目描述 Description Lele 最近上课的时候都很无聊,所以他发明了 ...
-
codevs 1229 数字游戏(可重集的全排列)
传送门 Description Lele 最近上课的时候都很无聊,所以他发明了一个数字游戏来打发时间. 这个游戏是这样的,首先,他拿出几张纸片,分别写上0到9之间的任意数字(可重复写某个数字),然后 ...
随机推荐
-
【Java学习系列】第2课--Java语法及面向对象
本文地址 分享提纲: 1. Java程序特点 1.1 基本语法 1.2 字符串 1.3 变量 1.4 Java数组 1.5 Java枚举 1.6 Java修饰符 1.7 Java编译制定在制定目录 2 ...
-
浮点数转换为人名币读法字符串(JAVA)
/*<java疯狂讲义>浮点数转换为人名币读法字符串这个用例,感觉没有考虑零的情况*/ import java.util.Arrays; public class Num2Rmb { pr ...
-
Java异常机制
Java异常分类 异常表明程序运行发生了意外,导致正常流程发生错误,例如数学上的除0,打开一个文件但此文件实际不存在,用户输入非法的参数等.在C语言中我们处理这类事件一般是将其与代码正常的流程放在一起 ...
-
彷徨中的成长-记一个文科生的IT成长过程
纠结了许久,要不要写这篇文章,然而最终还是写了.就权当总结与呻吟吧..当然,呻吟最开始还是发在自己的站点的,忍不住手贱,还是想发博客园. 1 剧透 人算不如天算:时隔多年,我竟然搞起了前端. 2 发端 ...
-
Research Papers
NSE, $\bbu$ [Papers]NSE, $u$, Lorentz space [Sohr, JEE, 2001] [Papers]NSE, $u$, Lorentz space [Bjorl ...
-
vue 项目中添加阿里巴巴矢量图
1. 选择需要的图标,添加到购物车 2. 打开购物车,添加至我的项目 3. 打开项目列表 - 更多操作 - 编辑项目 修改FontClass/Symbol前缀,自定义一个名称,例如:v-icon-cu ...
-
基于Kafka消息驱动最终一致事务(二)
实现用例分析 上篇基于Kafka消息驱动最终一致事务(一)介绍BASE的理论,接着我们引入一个实例看如何实现BASE,我们会用图7显示的算法实现BASE.
-
node 报错:Uncaught Error: Cannot find module ";!!../../../node_modules/extract-webpack-plugin/loader.js
问题出在缺少less和less-loader 因为以上模块使用了less解析. 解决方法在dependencies添加 "less": "^2.7.1", & ...
-
【ACM-ICPC 2018 徐州赛区网络预赛】E. End Fantasy VIX 血辣 (矩阵运算的推广)
Morgana is playing a game called End Fantasy VIX. In this game, characters have nn skills, every ski ...
-
HTML注册页面验证注册信息
在这里主要介绍两种验证方式,一种是点击注册按钮后会提示最上方的出错位置,弹出窗口提示格式不对.另一种是利用鼠标事件,在鼠标进行不同操作时会有不同的click事件. 这两种都是利用javascript, ...