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

【生日蛋糕——DFS剪枝优化】

题目

分析

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 24;
const int inf = 0x3f3f3f3f;

int mins[N], minv[N];
int R[N], H[N];
int n, m, ans = inf;

void dfs(int u, int v, int s)
{
    if(v + minv[u] > n) return;
    
    if(s + mins[u] >= ans) return;
    if(s + 2 * (n - v) / R[u+1] >= ans) return;
    
    if(!u)
    {
        if(v == n) ans = s;
        return;
    }
    
    for(int r = min( R[u+1]-1, (int)sqrt((n - minv[u-1] - v) / u) ); r >= u; r--)
        for(int h = min( H[u+1]-1, (n - minv[u-1] - v) / r / r); h >= u; h--)
        {
            R[u] = r, H[u] = h;
            int t = u == m ? r * r : 0;
            dfs(u-1, v + r*r*h, s + 2*r*h + t);
        }
}
int main()
{
    scanf("%d%d", &n, &m);
    
    for(int i = 1; i <= m; i++)
    {
        minv[i] = minv[i-1] + i * i * i;
        mins[i] = mins[i-1] + 2 * i * i;
    }
    
    R[m+1] = H[m+1] = inf;
    dfs(m, 0, 0);
    
    if(ans > inf / 2) ans = 0;
    printf("%d", ans);
}


http://www.kler.cn/a/587593.html

相关文章:

  • 网络安全系统集成
  • 微信小程序项目 tabBar 配置问题:“pages/mine/mine“ need in [“pages“]
  • 缓存之美:Guava Cache 相比于 Caffeine 差在哪里?
  • 游戏引擎学习第157天
  • neo4j中常用cql命令汇总(基础版)
  • Spark eventlog
  • [文献阅读] 可变形卷积DCN - Deformable Convolutional Networks
  • 服务性能防腐体系:基于自动化压测的熔断机制
  • 【软考-架构】3.4、数据库新技术-SQL语言
  • 基于牛优化( OX Optimizer,OX)算法的多个无人机协同路径规划(可以自定义无人机数量及起始点),MATLAB代码
  • 【eNSP实战】将路由器配置为DHCP服务器
  • 数据库原理10
  • 锂电池保护板测试仪:守护能源安全的科技卫士
  • 【STM32】USART串口收发HEX数据包收发文本数据包
  • 力扣 11.盛水最多的容器(双指针)
  • QT核心类:基础类、GUI类、多媒体与图表、网络与数据库
  • 游戏引擎学习第160天
  • 【GPT入门】第21课 langchain核心组件
  • vscode--工作区和相对路径
  • 【Linux内核系列】:文件系统收尾以及软硬链接详解