2 条题解
-
0杨竣然 (Edric) LV 9 @ 2024-2-1 14:10:08
#include <iostream> #include<bits/stdc++.h> #define int long long const int INF=0x3f3f3f3f; using namespace std; int n,m; int minn=INF; void dfs(int r, int h, int v,int s,int step){ if(step==m+1){ if(v==n){ minn=min(minn,s); } return; } if(v+m-step+1>n) return; if(v+(m-step+1)*((r-1)*(r-1)*(h-1))<n) return; if(s+2*(n-v)/r>=minn) return; for(int i=r-1;i>=m-step+1;i--){ for(int j=h-1;j>=m-step+1;j--){ dfs(i,j,v+i*i*j,s+2*i*j,step+1); } } } signed main(){ cin>>n>>m; for(int i=m;i*i*m<=n;i++){ for(int j=m;j<=n;j++){ if(2*i*j+i*i<minn){ dfs(i,j,i*i*j,2*i*j+i*i,2); } } } if(minn!=INF){ cout<<minn; }else{ cout<<0; } return 0; }
-
02023-4-23 19:13:11@
废话不说了 上代码
#include <iostream> #include <algorithm> #include<string.h> using namespace std; int mins=100000; int n,m; void dfs(int ceng,int v,int s,int r,int h)//依次为剩余层数,剩余体积,已有面积,此时半径,此时高 { //剪枝操作,解题时可以先从下方循环操作开始写 if(v>ceng*(r-1)*(h-1)*(r-1)&&m!=ceng) return;// 当剩余体积大于 “以现在的r和h能达到的最大体积” // 时,不用继续了,剪枝 if(v<0) return;//当剩余体积小于了0时,剪枝 if(ceng==0)//当层数为零(即已经达到题目要求) 时 { if(v==0&&s<mins) { mins=s;//当体积刚好用完,并且面积小于最小面积时,更新最小值 } return; } if(s>mins) return;//此时面积大于最小面积,剪枝 for(int i=r-1;i>=ceng;i--) for(int j=h-1;j>=ceng;j--)//对当前r至最小r,当前h至最小h,所有情况进行搜索 { int cv=i*i*j;int cs=2*i*j;// 附加体积cv,附加面积cs(附加面积相当于只 //加上侧面积,所有层顶面积之和等于最底层顶面积) if(ceng==m) cs+=i*i;//当时第一层时,加上最底层顶面积 if(s+2*v/i>mins&&mins!=0) continue;// 剩余体积为 (πr^3)*h , 可增加最小面积为 // 2πr^2 * h ,如果大于,则剪枝 dfs(ceng-1,v-cv,s+cs,i,j);//现在的r和h,剩余可用层数,剩余体积,已有面积 } } int main() { scanf("%d%d",&n,&m); dfs(m,n,0,100,10000);// printf("%d",mins); }
- 1
信息
- ID
- 79
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 3
- 标签
- 递交数
- 64
- 已通过
- 33
- 上传者