描述
给出n个数围成一个环,将其划分成k个部分,每个部分求和再对10取模,最后将每个部分的值相乘,求其最大值与最小值.
描述
丁丁最近沉迷于一个数字游戏之中。这个游戏看似简单,但丁丁在研究了许多天之后却发 觉原来在简单的规则下想要赢得这个游戏并不那么容易。游戏是这样的,在你面前有一圈整数(一共n个),你要按顺序将其分为m个部分,各部分内的数字相加, 相加所得的m个结果对10取模后再相乘,最终得到一个数k。游戏的要求是使你所得的k最大或者最小。
格式
输入格式
输入文件第一行有两个整数,n(1≤n≤50)和m(1≤m≤9)。以下n行每行有个整数,其绝对值不大于104,按顺序给出圈中的数字,首尾相接。
输出格式
输出文件有两行,各包含一个非负整数。第一行是你程序得到的最小值,第二行是最大值。
限制
各个测试点1s
提示
DP!^_^
分析
简单的划分型dp.转移方程:
dp[i][k]=max{dp[j][k-1]*(s[i]-s[j-1])}.
注意:
1.取模.
2.初始化.
#include <bits/stdc++.h>
using namespace std; const int maxn=+,maxk=+,INF=0x7fffffff; int n,K,ans1,ans2;
int s[maxn<<];
int dp1[maxn][maxk],dp2[maxn][maxk]; int num(int x){ return((x%)+)%; }
void solve(){
ans1=INF,ans2=-INF;
for(int q=;q<=n;q++){
for(int i=;i<=n;i++) dp1[i][]=dp2[i][]=num(s[q-+i]-s[q-]);
for(int k=;k<=K;k++)
for(int i=k;i<=n;i++){
dp1[i][k]=INF,dp2[i][k]=-INF;
for(int j=k-;j<i;j++){
dp1[i][k]=min(dp1[i][k],dp1[j][k-]*num(s[q-+i]-s[q-+j]));
dp2[i][k]=max(dp2[i][k],dp2[j][k-]*num(s[q-+i]-s[q-+j]));
}
}
ans1=min(ans1,dp1[n][K]);
ans2=max(ans2,dp2[n][K]);
}
printf("%d\n%d\n",ans1,ans2);
}
void init(){
scanf("%d%d",&n,&K);
for(int i=;i<=n;i++){
int t; scanf("%d",&t);
s[i]=s[i-]+t;
}
for(int i=n+;i<=*n;i++) s[i]=s[n]+s[i-n];
}
int main(){
init();
solve();
return ;
}
Vijos_1218_数字游戏_(划分型动态规划+环状动态规划)的更多相关文章
-
Codevs_1040_[NOIP2001]_统计单词个数_(划分型动态规划)
描述 http://codevs.cn/problem/1040/ 与Codevs_1017_乘积最大很像,都是划分型dp. 给出一个字符串和几个单词,要求将字符串划分成k段,在每一段中求共有多少单词 ...
-
java实现登录的验证码和猜数字游戏_图形化界面
实验任务四 1,出现设计思想 (1)先定义文本框.密码框和验证码框的组件 (2)定义面板和按钮的个数 (3)定义公有的虚构方法,通过对象实例化来调用 (4)利用Random类来实现生成0-9的随机数 ...
-
Codevs_1017_乘积最大_(划分型动态规划/记忆化搜索)
描述 http://codevs.cn/problem/1017/ 给出一个n位数,在数字中间添加k个乘号,使得最终的乘积最大. 1017 乘积最大 2000年NOIP全国联赛普及组NOIP全国联赛提 ...
-
codevs1085数字游戏(环形DP+划分DP )
1085 数字游戏 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 丁丁最近沉迷于一个数字游戏之中.这个游戏看似简单, ...
-
[蓝桥杯]PREV-23.历届试题_数字游戏
问题描述 栋栋正在和同学们玩一个数字游戏. 游戏的规则是这样的:栋栋和同学们一共n个人围坐在一圈.栋栋首先说出数字1.接下来,坐在栋栋左手边的同学要说下一个数字2.再下面的一个同学要从上一个同学说的数 ...
-
Codevs 1085 数字游戏
1085 数字游戏 2003年NOIP全国联赛普及组 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 丁丁最近沉迷于一个数字游戏之中 ...
-
不一样的猜数字游戏 — leetcode 375. Guess Number Higher or Lower II
好久没切 leetcode 的题了,静下心来切了道,这道题比较有意思,和大家分享下. 我把它叫做 "不一样的猜数字游戏",我们先来看看传统的猜数字游戏,Guess Number H ...
-
Java完成简单猜数字游戏v2.0
猜数字游戏v2.0 优化了获取随机数.输入数据超出边界值的代码,并增加了异常处理,能够在玩家输入错误数据错误时给出可靠指引,希望对和我一样的新人有帮助, 最后希望有大神愿意帮我解决代码优化的问题,谢谢 ...
-
猜数字游戏--基于python
"""题目:练习使用python写一个猜数字的游戏,数字范围0-100,每次猜错,需要给出缩小后的范围,每个人只有10次的猜测机会,猜测机会用完游戏结束!"&q ...
随机推荐
-
swift 如何实现点击view后显示灰色背景
有这样一种场景,当我们点击view的时候,需要过0.几秒显示一个灰色或者别的颜色的背景 用button来实现,只有按下去的时候才会出现,往往在快速按下,快速抬起的时候是看不出这个变化的 下边是解决方案 ...
-
Gradle用户指南(1)-Gradle安装
前置条件 Gradle 需要 Java JDK 或者 JRE,版本是 6 及以上.Gradle 将会装载自己的 Groovy 库,因此,Groovy 不需要被安装.任何存在的 Groovy 安装都会被 ...
-
python简单粗暴多进程之concurrent.futures
python在前面写过多线程的库threading: python3多线程趣味详解 但是今天发现一个封装得更加简单暴力的多进程库concurrent.futures: # !/usr/bin/pyth ...
-
【面试题042】翻转单词顺序VS左旋转字符串
[面试题042]翻转单词顺序VS左旋转字符串 题目一: 输入一个英文句子,反转句子中单词的顺序,但单词内字符的顺序不变.为简单起见,标点符号和普通字母一样处理. 例如输入字符串“I a ...
-
EDIT Ini写Ini配置
EDIT Ini写Ini配置 uses IniFiles; {$R *.dfm} function IniFileName:string; begin Result:=ExtractFil ...
-
hdu3368之DFS
Reversi Time Limit: 5000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Su ...
-
[小技巧] 打造属于 Dell XPS 13 (9350) 的专属 Windows 7 iso 镜像
MacBook Air 13, Dell XPS 13 和 Thinkpad X1 Carbon 都是轻薄笔记本中设计优秀的典范,受到很多用户追捧. 不过对于 Windows 阵营的笔记本,最近有个坏 ...
-
windows phone 加速计(5)
原文:windows phone 加速计(5) 在windows phone 中存在着加速计,我们可以利用加速计获得用户手机的状态,根据手机状态调整我们的程序,这样会更人性化:windows phon ...
-
在fetch方法中添加header后遇到的预检请求问题
今天在使用fetch方法 fetch('xxx.com',{header:{bbbbbbb:111}}) 浏览器返回的请求信息中,header变成了 :authority:koss.nocorp.me ...
-
「WC2018」通道
没有代码能力... LOJ #2339 Luogu P4220 UOJ #347 题意 给定三棵树$ T1,T2,T3$,求一个点对$ (x,y)$使得$ T1.dist(x,y)+T2.dist(x ...