首页 > 其他分享 >AcWing 414. 数字游戏

AcWing 414. 数字游戏

时间:2023-09-27 16:01:13浏览次数:42  
标签:10 游戏 int large 最大值 414 最小值 AcWing

\(AcWing\) \(414\). 数字游戏

一、题目描述

丁丁最近沉迷于一个数字游戏之中。

这个游戏看似简单,但丁丁在研究了许多天之后却发觉原来在简单的规则下想要赢得这个游戏并不那么容易。

游戏是这样的,在你面前有一圈整数(一共 \(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\) 和 \(m\)。

以下 \(n\) 行每行一个整数,其绝对值不大于 \(10000\),按顺序给出圈中的数字,首尾相接。

输出格式
输出文件有两行,各包含一个非负整数。

第一行是你程序得到的最小值,第二行是最大值。

数据范围
\(1≤n≤50,1≤m≤9\)

输入样例

4 2
4
3
-1
2

输出样例

7
81

二、题目解析

(\(DP\),区间\(DP\)) \(O(n^3m)\)

首先 将环从起点处断开,然后复制一遍接在后面,这样原问题就转化成了线段型的模型。

注:破环成链

n = read(), m = read();
for (int i = 1; i <= n; i ++ ){
    w[i] = read();
    w[i + n] = w[i]; //破环成链
}

然后 从集合角度来分析状态表示和状态计算

状态表示

\(f[l][r][k]\):所有将区间\([l,r]\)划分成\(k\)部分方案的乘积 最大值
\(g[l][r][k]\):所有将区间\([l,r]\)划分成\(k\)部分方案的乘积 最小值

状态计算

考虑\(f[l][r][k]\)如何计算获得,关键是寻找 集合划分的依据,划分依据一般选取 最后一步的操作,所以这里我们可以 按最后一部分的位置来将\(f[l][r][k]\)所表示的所有方案划分成若干类

注:上面的是数字的点,而不是区间,不要混淆!可能会造成理解错误~

注:第\(k\)个部分,肯定是从\(k-1\)个部分转移而来,现在考虑的是划分完\(k-1\)部分后,最后一个点的所有可能性\([l+k-2,r-1]\)

不妨设原\(k-1\)部分的终点是\(j\),所以

\[\large l+k-2<=j<=r-1 \]

注:\(j\)是可以遍历的

思考增加了第\(k\)个部分,最大值、最小值怎么求呢?

前\(k-1\)个部分的终点是\(j\),第\(k\)个部分的起点是从\([j+1,r]\)的任意一个值。
就是

\[\large f[l][r][k]= f[l][j][k-1] * (sum(r)-sum(j+1)) \\ \large g[l][r][k]= g[l][j][k-1] * (sum(r)-sum(j+1))\]

解释
因为对于每个方案而言,它的得分就是前面的数乘上后面的数。
由于每个数都是非负的,如果我希望我最终的结果是最大值或最小值,而且,现在后面黄色方框中的数字大小是固定的,所以,前面最大就是整体最大,前面最小就是整体最小。

最终枚举所有长度是\(n\)的区间,取最大值/最小值即可。
\(\large f[i][i+n][m] \\ \large g[i][i+n][m]\)

时间复杂度
状态总共有 \(O(n^2m)\) 个,计算每个状态需要 \(O(n)\) 的计算量,因此总时间复杂度是 \(O(n^3m)\)。

三、实现代码

#include <bits/stdc++.h>
using namespace std;
const int N = 110, M = 10, INF = 0x3f3f3f3f;

int n, m;
int w[N], s[N];
int f[N][N][M], g[N][N][M];

int get_mod(int x) {
    return (x % 10 + 10) % 10;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> w[i];
        w[i + n] = w[i]; // 破环成链
    }
    for (int i = 1; i <= n * 2; i++) s[i] = s[i - 1] + w[i]; // 预处理前缀和,下标从1开始

    memset(f, 0x3f, sizeof f);  // 预求最小,先设最大
    memset(g, -0x3f, sizeof g); // 预求最大,先设最小

    for (int len = 1; len <= n; len++)               // 区间DP,先枚举长度
        for (int l = 1; l + len - 1 <= n * 2; l++) { // 枚举起点
            int r = l + len - 1;                     // 计算终点
            // DP 初始化
            // 边界条件是全部划分为k=1,也就是一块时的结果是多少,根据题意,一整块当然就是区间内容相加后对10取模
            f[l][r][1] = g[l][r][1] = get_mod(s[r] - s[l - 1]);
            // 状态转移
            for (int k = 2; k <= m; k++)                   // 枚举每个可以划分成的部分
                for (int j = l + k - 2; j <= r - 1; j++) { // 枚举K-1部分时的最后一个终点位置
                    f[l][r][k] = min(f[l][r][k], f[l][j][k - 1] * get_mod(s[r] - s[j]));
                    g[l][r][k] = max(g[l][r][k], g[l][j][k - 1] * get_mod(s[r] - s[j]));
                }
        }

    // 枚举每个区间长度为n的区间,获取符合长度要求的区间内,划分成m块的最大、最小值
    int mx = -INF, mi = INF;
    for (int i = 1; i <= n; i++) {
        mx = max(mx, g[i][i + n - 1][m]);
        mi = min(mi, f[i][i + n - 1][m]);
    }
    cout << mi << endl;
    cout << mx << endl;
    return 0;
}

标签:10,游戏,int,large,最大值,414,最小值,AcWing
From: https://www.cnblogs.com/littlehb/p/17732898.html

相关文章

  • 506_杂牌手柄游戏不适配?Steam这项功能其实就能解决
    这是一篇原发布于2020-03-2812:37:00得益小站的文章,备份在此处。前言市场上游戏手柄虽多,但PC游戏中做到能够适配的似乎也只有Xbox、PS、SwitchPro等大厂发布的手柄。即使游戏中有着手柄按键设置,但无法完美显示XYAB键、按键命名混乱一直是游戏玩家的硬伤。配置效果对比轶哥测......
  • 01 - Rust 猜数字游戏
    目录1.猜数字游戏的逻辑2.创建新项目3.猜数字游戏实现3.1获取用户输入并打印a.标准库引入b.println!宏c.可变与不可变变量d.string::new与io::stdin().read_line(&mutinput)3.2生成指定范围内的随机数3.3随机数与猜测数的比较a.字符串转数字b.数字比较大小c.循环......
  • 策略游戏
    P8818[CSP-S2022]策略游戏以下的分析,定义正数\(\ge0\),负数\(\le0\)。我们发现,如果第一个人取了正数,第二个人如果有负数,那么就取绝对值最大的负数,即最小的数;如果没有,就取最小的正数,也是最小的数。如果第一个人取了负数,第二个人如果有正数,那么就取最大的正数,即最大的数;如......
  • AcWing 463. 求和
    \(AcWing\)\(463\).求和一、题目描述一条狭长的纸带被均匀划分出了\(n\)个格子,格子编号从\(1\)到\(n\)。每个格子上都染了一种颜色\(color_i\)(用\([1,m]\)当中的一个整数表示),并且写了一个数字\(number_i\)。定义一种特殊的三元组:\((x,y,z)\),其中\(x,y,z\)都代表纸......
  • 第九十八场周赛. AcWing 4949. 末尾连续0
    第九十八场周赛.AcWing4949.末尾连续0给定一个正整数\(m\),请你统计一共有多少个正整数\(n\)满足,\(n\)的阶乘的末尾连续\(0\)的数量恰好为\(m\)。输出满足条件的\(n\)的数量以及所有满足条件的\(n\)。例如,当\(m=1\)时,满足条件的正整数\(n\)共有......
  • 第九十八场周赛. AcWing 4948. 大乘积
    第九十八场周赛.AcWing4948.大乘积我们规定,如果一个非负整数\(a\)满足以下两个条件之一,则称\(a\)为美丽数:\(a=0\)\(a=10^x\),其中\(x\)为任意非负整数。给定\(n\)个非负整数\(a_1,a_2,…,a_n\),这其中有至少\(n−1\)个数是美丽数。请你计算并输出\(a_......
  • 2022年抖音最近很火的游戏直播:挤地铁教程+源码+软件
    音最近很火的游戏直播:挤地铁教程+源码+软件先上车先吃肉,卡好后带货,卖号,引私域,接星途广告,接小程序广告,带小游戏赚收益均可。有需要的材料自取:提取码:9jbw ......
  • AcWing 896. 最长上升子序列 II
    题目给定一个长度为$N$的数列,求数值严格单调递增的子序列的长度最长是多少。输入格式第一行包含整数$N$。第二行包含$N$个整数,表示完整序列。输出格式输出一个整数,表示最大长度。数据范围$1≤N≤100000,−10^9≤数列中的数≤10^9$输入样例:73121856输出样例......
  • GPT 被曝重大缺陷;腾讯侦破国内首个 AI 游戏外挂;特斯拉人形机器人再进化丨 RTE 开发者
    开发者朋友们大家好:这里是「RTE开发者日报」,每天和大家一起看新闻、聊八卦。我们的社区编辑团队会整理分享RTE(RealTimeEngagement)领域内「有话题的新闻」、「有态度的观点」、「有意思的数据」、「有思考的文章」、「有看点的会议」,但内容仅代表编辑的个人观点,欢迎大家留......
  • 【Python入门教程】Python实现猜数字小游戏
    ​    今天跟大家分享一下很久之前自己做的一款猜数字小游戏,基本的循环判断语句即可实现,可以用来当练手或者消磨时间用。    大家在编代码的时候最重要就是先理清逻辑思路,例如应该套几层循环、分几个模块等等。然后在编码时可以先随意一点,变量名、函数等可以先......