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

个人网站做音乐网要备文化深圳居家办公

个人网站做音乐网要备文化,深圳居家办公,网站推广工具网络,软件开发工具的基础是这道题最后有一个性质没有想出来,感觉还是有一点遗憾。 性质一、贪心是不对的 8 11 11 16虽然第一次选择8和16合并是最优的,但是如果合并两次的话8 11 11是最优的。 性质二 、有1的情况就是前k1个,也就是说,很多情况下取前k1都…

这道题最后有一个性质没有想出来,感觉还是有一点遗憾。

性质一、贪心是不对的

8 11 11 16

虽然第一次选择8和16合并是最优的,但是如果合并两次的话8 11 11是最优的。

性质二 、有1的情况就是前k+1个,也就是说,很多情况下取前k+1都是最优的

性质三 如果某个数前面有它的因子,那么合并的时候可以不对 a 1 a_1 a1产生任何影响。同时,如果 b m o d a = 0 , b > a b \mod a=0,b>a bmoda=0,b>a那么 b b b一定比 a a a后合并,也就是说无影响合并只会发生在相同的数之间,因此我们把无影响的数提出来考虑,所以剩下的都是不同的。

性质四 如果所有的数都不同,那么全部都只会和 a 1 a_1 a1合并。在原来的数列中考虑合并形成的连通块。在连通块大小为2的情况时。设 a 1 < x < y a1<x<y a1<x<y,那么有 y − x > = g c d ( x , y ) y-x>=gcd(x,y) yx>=gcd(x,y)所以, x + y − g c d ( x , y ) > = 2 x > a 1 + x x+y-gcd(x,y)>=2x>a_1+x x+ygcd(x,y)>=2x>a1+x,不如直接合并 a 1 a_1 a1 x x x。现在考虑连通块大小超过2的情况。假设某个连通块不包含 1 1 1,那么我们可以通过合并使得该联通块剩下两个数,其中有一个还没有与任何的数合并。Case 1: x < a 1 < y x<a_1<y x<a1<y,这时应该合并 x , a 1 x,a_1 x,a1最优,与原假设矛盾。Case 2: a 1 < = x < = y a_1<=x<=y a1<=x<=y,这时也是合并 a 1 , x a_1,x a1,x更优,所以假设错误。

所以,现在应该把前面有相同的和剩下的全部不同的数分成两个组,然后给这两组分配合并次数,难点就是要怎么求在给定的次数时全部不同组的选择方法,但是我没有坚定的往这个方面想。

性质五 假设给全部不同的数合并 k k k次,那么必然选择 1 , 2 , . . . , k − 1 1,2,...,k-1 1,2,...,k1,只有第 k k k个是不确定的。考虑选择 a , b , c , d ( a < b < c < d ) a,b,c,d(a<b<c<d) a,b,c,d(a<b<c<d)的情况,那么合并如果是 a , c , d a,c,d a,c,d的话,那么 c o s t ( a , c , d ) − c o s t ( a , b , c ) = d − b + g c d ( a , c , d ) − g c d ( a , b , c ) > = g c d ( b , c ) + g c d ( c , d ) + g c d ( a , c , d ) − g c d ( a , b , c ) > 0 cost(a,c,d)-cost(a,b,c)=d-b+gcd(a,c,d)-gcd(a,b,c)>=gcd(b,c)+gcd(c,d)+gcd(a,c,d)-gcd(a,b,c)>0 cost(a,c,d)cost(a,b,c)=db+gcd(a,c,d)gcd(a,b,c)>=gcd(b,c)+gcd(c,d)+gcd(a,c,d)gcd(a,b,c)>0,所以只用考虑第k个点怎么选,而且枚举范围有 a [ i ] − a [ k − 1 ] < g c d ( a 1 , a 2 , . . . , a k − 1 ) a[i]-a[k-1]<gcd(a_1,a_2,...,a_{k-1}) a[i]a[k1]<gcd(a1,a2,...,ak1),这样显然是不超过 O ( n l o g n ) O(nlogn) O(nlogn)的。

http://www.dt0577.cn/news/20540.html

相关文章:

  • 青岛黄岛网站建设公司电话计算机培训班培训费用
  • 广告网站建设案例计算机培训班
  • 网站源码超市萧山区seo关键词排名
  • 上海宝山网站建设爱站网络挖掘词
  • 网站建设需2023广州疫情最新消息今天
  • 网站域名后缀cc西安百度竞价开户
  • 商务网站要怎么做网站关键词优化建议
  • 视频网站直播怎么做的友链互换平台推荐
  • 做新媒体的小说网站凡科建站靠谱吗
  • 需要做网站的企业电话线上广告推广平台
  • 一起做业官方网站百度搜索引擎的网址是多少
  • 博山政府网站建设哪家好湖南长沙seo
  • 深圳外贸进出口公司排名西安百度关键词优化
  • c2c的电子商务网站有哪些惠州seo优化
  • h5css3网站开发实例友情链接属于免费推广吗
  • 怎样做化妆品公司网站百度有几个总部
  • 山东建设厅官方网站临沂网络营销策略有哪五种
  • 做阿里巴巴网站口碑怎样注册自己网站的域名
  • 做网站内嵌地图今日nba战况
  • 白塔网站建设seo人才招聘
  • 宽城区建设局网站网盟推广
  • 做6个页面的网站杨谦教授编的营销课程
  • wordpress挂下载链接seo优化服务商
  • 网站设计有哪些创新点关键词seo排名怎么做的
  • 建一个网站的程序谷歌排名优化
  • 网站建设公司哪家好 搜搜磐石网络包就业的培训机构
  • 如何制作活动宣传网页长春seo关键词排名
  • 做网站建设客户从哪里找seo外链发布技巧
  • 做视频网站需要多少钱重庆百度seo公司
  • wordpress 一直跳转到老域名一键优化清理加速