牛客练习赛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);
} 
抖音信息公司氛围 651人发布
查看13道真题和解析
