Vijos_1218_数字游戏_(划分型动态规划+环状动态规划)

时间:2022-07-12 00:31:14

描述


https://vijos.org/p/1218

给出n个数围成一个环,将其划分成k个部分,每个部分求和再对10取模,最后将每个部分的值相乘,求其最大值与最小值.

描述

丁丁最近沉迷于一个数字游戏之中。这个游戏看似简单,但丁丁在研究了许多天之后却发 觉原来在简单的规则下想要赢得这个游戏并不那么容易。游戏是这样的,在你面前有一圈整数(一共n个),你要按顺序将其分为m个部分,各部分内的数字相加, 相加所得的m个结果对10取模后再相乘,最终得到一个数k。游戏的要求是使你所得的k最大或者最小。

格式

输入格式

输入文件第一行有两个整数,n(1≤n≤50)和m(1≤m≤9)。以下n行每行有个整数,其绝对值不大于104,按顺序给出圈中的数字,首尾相接。

输出格式

输出文件有两行,各包含一个非负整数。第一行是你程序得到的最小值,第二行是最大值。

样例1

样例输入1[复制]

4 2
4
3
-1
2

样例输出1[复制]

7
81

限制

各个测试点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_数字游戏_(划分型动态规划+环状动态规划)的更多相关文章

  1. Codevs&lowbar;1040&lowbar;&lbrack;NOIP2001&rsqb;&lowbar;统计单词个数&lowbar;&lpar;划分型动态规划&rpar;

    描述 http://codevs.cn/problem/1040/ 与Codevs_1017_乘积最大很像,都是划分型dp. 给出一个字符串和几个单词,要求将字符串划分成k段,在每一段中求共有多少单词 ...

  2. java实现登录的验证码和猜数字游戏&lowbar;图形化界面

    实验任务四 1,出现设计思想 (1)先定义文本框.密码框和验证码框的组件 (2)定义面板和按钮的个数 (3)定义公有的虚构方法,通过对象实例化来调用 (4)利用Random类来实现生成0-9的随机数 ...

  3. Codevs&lowbar;1017&lowbar;乘积最大&lowbar;&lpar;划分型动态规划&sol;记忆化搜索&rpar;

    描述 http://codevs.cn/problem/1017/ 给出一个n位数,在数字中间添加k个乘号,使得最终的乘积最大. 1017 乘积最大 2000年NOIP全国联赛普及组NOIP全国联赛提 ...

  4. codevs1085数字游戏(环形DP&plus;划分DP )

    1085 数字游戏  时间限制: 1 s  空间限制: 128000 KB  题目等级 : 黄金 Gold     题目描述 Description 丁丁最近沉迷于一个数字游戏之中.这个游戏看似简单, ...

  5. &lbrack;蓝桥杯&rsqb;PREV-23&period;历届试题&lowbar;数字游戏

    问题描述 栋栋正在和同学们玩一个数字游戏. 游戏的规则是这样的:栋栋和同学们一共n个人围坐在一圈.栋栋首先说出数字1.接下来,坐在栋栋左手边的同学要说下一个数字2.再下面的一个同学要从上一个同学说的数 ...

  6. Codevs 1085 数字游戏

    1085 数字游戏 2003年NOIP全国联赛普及组 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 丁丁最近沉迷于一个数字游戏之中 ...

  7. 不一样的猜数字游戏 — leetcode 375&period; Guess Number Higher or Lower II

    好久没切 leetcode 的题了,静下心来切了道,这道题比较有意思,和大家分享下. 我把它叫做 "不一样的猜数字游戏",我们先来看看传统的猜数字游戏,Guess Number H ...

  8. Java完成简单猜数字游戏v2&period;0

    猜数字游戏v2.0 优化了获取随机数.输入数据超出边界值的代码,并增加了异常处理,能够在玩家输入错误数据错误时给出可靠指引,希望对和我一样的新人有帮助, 最后希望有大神愿意帮我解决代码优化的问题,谢谢 ...

  9. 猜数字游戏--基于python

    """题目:练习使用python写一个猜数字的游戏,数字范围0-100,每次猜错,需要给出缩小后的范围,每个人只有10次的猜测机会,猜测机会用完游戏结束!"&q ...

随机推荐

  1. swift 如何实现点击view后显示灰色背景

    有这样一种场景,当我们点击view的时候,需要过0.几秒显示一个灰色或者别的颜色的背景 用button来实现,只有按下去的时候才会出现,往往在快速按下,快速抬起的时候是看不出这个变化的 下边是解决方案 ...

  2. Gradle用户指南&lpar;1&rpar;-Gradle安装

    前置条件 Gradle 需要 Java JDK 或者 JRE,版本是 6 及以上.Gradle 将会装载自己的 Groovy 库,因此,Groovy 不需要被安装.任何存在的 Groovy 安装都会被 ...

  3. python简单粗暴多进程之concurrent&period;futures

    python在前面写过多线程的库threading: python3多线程趣味详解 但是今天发现一个封装得更加简单暴力的多进程库concurrent.futures: # !/usr/bin/pyth ...

  4. 【面试题042】翻转单词顺序VS左旋转字符串

    [面试题042]翻转单词顺序VS左旋转字符串 题目一:     输入一个英文句子,反转句子中单词的顺序,但单词内字符的顺序不变.为简单起见,标点符号和普通字母一样处理.     例如输入字符串“I a ...

  5. EDIT Ini写Ini配置

    EDIT Ini写Ini配置  uses IniFiles; {$R *.dfm}   function IniFileName:string; begin    Result:=ExtractFil ...

  6. hdu3368之DFS

    Reversi Time Limit: 5000/2000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Su ...

  7. &lbrack;小技巧&rsqb; 打造属于 Dell XPS 13 &lpar;9350&rpar; 的专属 Windows 7 iso 镜像

    MacBook Air 13, Dell XPS 13 和 Thinkpad X1 Carbon 都是轻薄笔记本中设计优秀的典范,受到很多用户追捧. 不过对于 Windows 阵营的笔记本,最近有个坏 ...

  8. windows phone 加速计(5)

    原文:windows phone 加速计(5) 在windows phone 中存在着加速计,我们可以利用加速计获得用户手机的状态,根据手机状态调整我们的程序,这样会更人性化:windows phon ...

  9. 在fetch方法中添加header后遇到的预检请求问题

    今天在使用fetch方法 fetch('xxx.com',{header:{bbbbbbb:111}}) 浏览器返回的请求信息中,header变成了 :authority:koss.nocorp.me ...

  10. 「WC2018」通道

    没有代码能力... LOJ #2339 Luogu P4220 UOJ #347 题意 给定三棵树$ T1,T2,T3$,求一个点对$ (x,y)$使得$ T1.dist(x,y)+T2.dist(x ...