洛谷P1043 数字游戏

题目描述

丁丁最近沉迷于一个数字游戏之中。这个游戏看似简单,但丁丁在研究了许多天之后却发觉原来在简单的规则下想要赢得这个游戏并不那么容易。游戏是这样的,在你面前有一圈整数(一共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取模的结果均为非负值。

丁丁请你编写程序帮他赢得这个游戏。

输入输出格式

输入格式:

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

输出格式:

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

输入输出样例

输入样例#1: 

4 2
4
3
-1
2

输出样例#1: 

7
81

DpMin[i][j][k]表示i到j中切了k次的最小值

DpMax表示最大值

转移的时候枚举断点

左右两边相乘

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=2001;
const int INF=0x7fffff;
inline char nc()
{
    static char buf[MAXN],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
    char c=nc();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=nc();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=nc();}
    return x*f;
}
int DpMin[101][101][11];
int DpMax[101][101][11];
int a[MAXN];
int Query(int a)
{
    return ((a%10)+10)%10;
}
int main()
{
    #ifdef WIN32
    freopen("a.in","r",stdin);
    #else
    #endif
    int n=read(),m=read();
    for(int i=1;i<=n;i++)   a[i]=read(),a[i+n]=a[i];
    for(int i=1;i<=2*n;i++) a[i]+=a[i-1];
    
    for(int l=1;l<=2*n;l++)
      for(int r=l;r<=2*n;r++)
        DpMin[l][r][1]=DpMax[l][r][1]=Query(a[r]-a[l-1]);
            
    for(int i=2;i<=m;i++)
      for(int l=1;l<=2*n;l++)
        for(int r=l+i-1;r<=2*n;r++)
          DpMin[l][r][i]=INF;
    for(int i=2;i<=m;i++)//已经切了k次
        for(int l=1;l<=2*n;l++)
            for(int r=l+i-1;r<=2*n;r++)
                for(int k=l+i-2;k<r;k++)
                {
                    DpMin[l][r][i]=min(DpMin[l][r][i],DpMin[l][k][i-1]*Query(a[r]-a[k]));
                    DpMax[l][r][i]=max(DpMax[l][r][i],DpMax[l][k][i-1]*Query(a[r]-a[k]));
                }
    int AnsMax=0,AnsMin=INF;
    for(int i=1;i<=n;i++)
        AnsMax=max(AnsMax,DpMax[i][i+n-1][m]),
        AnsMin=min(AnsMin,DpMin[i][i+n-1][m]);
    printf("%d\n%d",AnsMin,AnsMax);
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏算法channel

程序员必知的算法和数据结构:2500字性能总结

以下5个步骤总结了此方法,依次为如下,我们设计的实验必须是可以重现的,我们形成的假设必须是具有真伪的。

8100
来自专栏灯塔大数据

每周学点大数据 | No.9递归——以阶乘为例

No.9期 递归——以阶乘为例 Mr. 王:我们介绍一个在计算机算法设计和程序设计中都非常常见的概念——递归。 小可:什么是递归呢? Mr. 王:从程序设计的...

35840
来自专栏小樱的经验随笔

CTF---编程入门第一题 循环

循环分值:10 来源: 北邮天枢战队 难度:易 参与人数:1478人 Get Flag:467人 答题人数:523人 解题通过率:89% 给出一个循环公式,对于...

392110
来自专栏CodingToDie

Python学习(十):有趣的字符串

第10 章 Python 字符串 学的到东西的事情是锻炼,学不到的是磨练 Table of Contents 字符串更新 转义字符 原始字符串 运算 连接 重复...

44070
来自专栏C语言及其他语言

[每日一题]矩阵乘法

本次的题目来源于C语言网比赛栏目八月月赛第一题,记得去试试看看自己能不能AC哦!!! 题目描述 给定一个N阶矩阵A,输出A的M次幂(M是非负整数) 例如: ...

37250
来自专栏计算机视觉与深度学习基础

HDU2066

神坑的题目 思路就是枚举起点,迪杰斯特拉求最短路径,再枚举终点(如果起点终点一起枚举可能会超时,也能勉强扯上动态规划的思想吧),求最短路径。 如果剪枝可以加一个...

24470
来自专栏C/C++基础

基数排序简介及其并行化

  基数排序号称线性时间排序算法中性能最好,速度最快的排序算法。本文将简要概括其算法思想,串行代码及其并行化。

15810
来自专栏Crossin的编程教室

真值表

逻辑判断是编程中极为常用的知识。之前的课我们已经说过,见第6课和第11课。但鉴于逻辑运算的重要性,今天我再把常用的运算结果总结一下,供大家参考。 这种被称为“真...

24540
来自专栏Python

面向对象的三大特性(封装、继承、多态)

继承 什么是继承 继承是一种创建新类的方式,在python中,新建的类可以继承一个或多个父类,父类又可称为基类或超类,新建的类称为派生类或子类 python中类...

2K90
来自专栏Java爬坑系列

【JAVA零基础入门系列】Day3 Java基本数据类型

  前两篇已经将开发环境搭建完成,如果你已经按之前的教程按部就班的完成了部署,那么世界上最优秀的编程语言之一和世界上最优秀的IDE之一已经出现在你的电脑上(此处...

23980

扫码关注云+社区

领取腾讯云代金券