牛客练习赛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

相关推荐

不对是145个人…嗯…&nbsp;大家都没发现秋招提前批来了嘛..笑死我了
牛客39712426...:投了也是浪费时间,之前投米实习,除了浪费我时间写笔试题没有任何反馈,懒得投了
26届校招投递进展
点赞 评论 收藏
分享
05-29 22:11
门头沟学院 Java
Elastic90:抛开学历造假不谈,这公司的招聘需求也挺怪的,Java开发还要求你有图文识别、移动端开发和c++的经验,有点逆天了。
点赞 评论 收藏
分享
代码飞升:别用口语,后端就写后端,前端就写前端,最后别光后悔
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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