题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
using namespace std;
const int N=25,INF=1e9;
int n,m;
int minv[N],mins[N];
int R[N],H[N];
int 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-v));r>=u;r--)
for(int h=min(H[u+1]-1,(n-v)/r/r);h>=u;h--)
{
int t=0;
if(u==m) t=r*r; //圆面积
R[u]=r,H[u]=h;
dfs(u-1,v+r*r*h,s+2*r*h+t);
}
}
int main()
{
cin>>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) ans=0;
cout<<ans<<endl;
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
老巴拉拉小魔仙了
hahaha,主要是怕再看的时候忘了,所以只是简单的注释了一下。