当前位置: 首页 > news >正文

连云港网页设计/seo优化个人博客

连云港网页设计,seo优化个人博客,电子商务安全问题 网站权限管理,郑州做营销型网站公司最佳加法表达式 有一个由1..9组成的数字串.问如果将m个加号插入到这个数字串中,在各种可能形成的表达式中,值最小的那个表达式的值是多少 解题思路 假定数字串长度是n,添完加号后,表达式的最后一个加号添加在第 i 个数字后面,那么整个表达式的最小值,就等于在前 i 个数字中插入…

 


                                       最佳加法表达式


有一个由1..9组成的数字串.问如果将m个加号插入到这个数字串中,在各种可能形成的表达式中,值最小的那个表达式的值是多少


解题思路

假定数字串长度是n,添完加号后,表达式的最后一个加号添加在第 i 个数字后面,那么整个表达式的最小值,就等于在前 i 个数字中插入 m – 1个加号所能形成的最小值,加上第 i + 1到第 n个数字所组成的数的值(i从1开始算)。



解题思路
设V(m,n)表示在n个数字中插入m个加号所能形成的表达式最小值,那么:
if m = 0,
V(m,n) = n个数字构成的整数
else if n < m + 1
V(m,n) = ∞
else
V(m,n) = Min{ V(m-1,i) + Num(i+1,n) } ( i = m ... n-1)
Num(i,j)表示从第i个数字到第j个数字所组成的数。数字编号从1开始算。此操
作复杂度是O(j-i+1)
总时间复杂度:O(mn 2 )

代码如下:#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;int dp[100][200];
char str[500];//dp[m][n]表示的是示在n个数字中插入m个加号所能形成的表达式最小值int change(int x,int y)
{int t=0;for(int i = x ; i <= y ; i++){t*=10;t+=(str[i]-'0');}return t;
}int main()
{int n,m;while(scanf("%d%d",&m,&n)!=EOF){scanf("%s",str+1);memset(dp,0,sizeof(dp));for(int i = 1 ; i <= m ; i++)for(int j = 1 ; j <= n ; j++)//初始化为无穷大dp[i][j]=99999999;for(int i = 1 ; i <= n ; i++)//如果m等于0,那么dp就等于从一加到ndp[0][i]=change(1,i);for(int i = 1 ; i <= m ; i++)//否则的话就剩第三种情况了for(int j = i ; j <= n ; j++)for(int k = i ; k <= j ; k++)dp[i][j]=min(dp[i][j],dp[i-1][k]+change(k+1,j));//(i-1)~k,k~j(k肯定大于i-1)printf("%d\n",dp[m][n]);}return 0;
}


转载于:https://www.cnblogs.com/nyist-xsk/p/7264910.html

http://www.jmfq.cn/news/4744747.html

相关文章:

  • 盘古百度推广靠谱吗/网站优化策略分析论文
  • 软件网站排名/如何推广小程序平台
  • 常州有哪些做阿里巴巴网站的/南昌seo排名外包
  • 网站开发维护多少钱/菏泽资深seo报价
  • 用iPhone做网站服务器/整合营销传播案例分析
  • 自己建网站有什么好处/清远今日头条最新消息
  • 网站建设河南公司/台州优化排名推广
  • 网站的空间与域名/深圳百度推广竞价托管
  • b2c网站建设平台/青岛最新消息
  • 江门专业网站建设价格/百度识图搜索
  • 网站建设昆明网络公司/枸橼酸西地那非片
  • 网站建设网站模板/网站排名优化手机
  • h5 网站模板/交换友情链接吧
  • 普陀大型网站建设/关键词优化排名用哪些软件比较好
  • 专业做皮草的网站/天津seo排名效果好
  • 软件公司网站源码/巨量数据分析入口
  • 网站建设基础问题/怎样做网站推广
  • 潍坊网站建设联系方式/怎么做一个公司网站
  • 蚌山网站建设/河南网站排名优化
  • 深圳罗湖做网站公司哪家好/云seo关键词排名优化软件
  • 北京做网站公司有哪些/下载百度app最新版到桌面
  • 汽车网站建设代理加盟/长沙的seo网络公司
  • 网站推广品牌/北京优化网站方法
  • 个人网站公安局备案/网站搜索排优化怎么做
  • 网站的建设过程/seo线上培训多少钱
  • 有做火币网这种网站的吗/搜图片找原图
  • 那个网站能找到人/seo网站优化软件价格
  • 网站怎么被黑/网络营销手段
  • win xp 个人网站免费建设/网络营销有哪些推广方法
  • 电子商务网站设计规划书/服务器