IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 2022山东省赛 B - Minimum Expression(dp) -> 正文阅读

[数据结构与算法]2022山东省赛 B - Minimum Expression(dp)

题目链接:点击查看

题目大意:给出一个长度为 n n n 的仅由数字 1 ? 9 1-9 1?9 组成的字符串,问恰好添加 m m m 个加号后,等式的最小值是多少

题目分析:不需要考虑前导 0 0 0,而且仅有加号,不难想到很经典的 d p [ i ] [ j ] dp[i][j] dp[i][j],代表前 i i i 个位置,划分了 j j j 段后的最小答案,转移方程也是经典的 d p [ i ] [ j ] = m i n 0 ≤ k < i ( d p [ k ] [ j ? 1 ] ) dp[i][j]=min_{0\le k < i}(dp[k][j-1]) dp[i][j]=min0k<i?(dp[k][j?1]),时间复杂度是 O ( n 3 ) O(n^3) O(n3),空间复杂度 O ( n 2 ) O(n^2) O(n2)

然后本题需要关注的是,需要用到高精度加法,所以空间复杂度如果正常去想的话,也是 O ( n 3 ) O(n^3) O(n3)

如何优化呢?有个需要想到的思维点是,因为有 m m m 个加号,所以最终需要分成 m + 1 m+1 m+1 段,我们令每一段的长度尽量相等一定是最优的

如此一来时间复杂度可以优化到 O ( n 2 ) O(n^2) O(n2),而空间复杂度也可以优化为 O ( n ? m ? n m = n 2 ) O(n * m * \frac{n}{m}=n^2) O(n?m?mn?=n2)

p y t h o n python python 写起来比较简单

代码:

n,m=map(int,input().split())
m=m+1
s=" "+input()
dp=[[-1 for j in range(1010)] for i in range(1010)]
len=n//m
dp[0][0]=0
for i in range(1,n+1):
    for j in range(1,min(i,m)+1):
        for k in range(i-len-2,i-len+3):
            if k>=j-1 and k<i and dp[k][j-1]!=-1:
                if dp[i][j]==-1 or dp[i][j]>dp[k][j-1]+int(s[k+1:i+1]):
                    dp[i][j]=dp[k][j-1]+int(s[k+1:i+1])
print(dp[n][m])
  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-05-27 17:24:44  更:2022-05-27 17:24:48 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/30 15:31:06-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码