牛客练习赛23 B题题解

题意为给一个n,每次n拆成u+v,价值为u*v,然后继续对u,v进行相同操作,直到所以数字都拆分成为1
对于一个数n,显然每次将起拆分成两个最相近的数贡献最大,但是直接递归求解会TLE,此时需要稍微进行优化
可以先通过线性递推预处理前1e6个:
dp[1] = 0;
for(int i = 2; i <= 1e6; ++i){
dp[i] = dp[i>>1] + dp[i+1>>1] + 1ll * (i>>1) * (i+1>>1);
}
然后再进行dfs求解即可
ll dfs(ll n){
  if(n <= 1e6){
    return dp[n];
  }
  return dfs(n>>1) + dfs(n+1>>1) + 1ll * (n>>1) * (n+1>>1); 
}

全部评论
显然不管你怎么拆,得分之和是相同的
点赞 回复 分享
发布于 2018-07-28 00:46
显然不管你说了什么  qls说的都是对的 
点赞 回复 分享
发布于 2018-07-28 08:18
 显然不管你说了什么  qls说的都是对的  
点赞 回复 分享
发布于 2018-07-28 00:50

相关推荐

不愿透露姓名的神秘牛友
07-04 15:36
点赞 评论 收藏
分享
05-12 17:00
门头沟学院 Java
king122:你的项目描述至少要分点呀,要实习的话,你的描述可以使用什么技术,实现了什么难点,达成了哪些数字指标,这个数字指标尽量是真实的,这样面试应该会多很多,就这样自己包装一下,包装不好可以找我,我有几个大厂最近做过的实习项目也可以包装一下
点赞 评论 收藏
分享
练习生懒羊羊:开飞机把这个公司创飞吧
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务