题目链接
https://www.luogu.org/problemnew/show/P1731
分析
这题真[哔]恶心，加了一堆奇奇怪怪的优化
首先明确一点,半径和高都必须是正整数,意味着它们最小为$1$
同时我们通过数学公式可以推得:当剩下体积$v$一定时，层数越少面积越小,也就是说, 越趋进一个圆柱面积越小.
于是我们可以预处理出搜索到每一层的最小剩余体积$miv[i]=miv[i-1]+i^3$
假设我们从下(第m层)往上(第1层)枚举
那么我们可以列出优化:
设定初始$r$范围为$[1,\sqrt{n/m}]$,$h$范围$[1,n/(m * m)]$
同时在$DFS$过程中我们枚举$r$从上次$DFS$的$pre_r-1$递减到现在搜索的层数$now$,再枚举$h$,则其上限为$min((left-miv[now-1])/(r * r),pre_h-1)$,$left$是还剩下的体积,而下限也为$now$
同时还有剪枝
我们可以通过剩余体积$left$预估出接下来面积最小值(虽然可能并不能达到)为$left * 2/pre_r$,如果预估最小值加上当前面积累计值已大于已有的答案,则直接返回;
同时相对于体积,我们已经预处理出每一层最小剩余体积,如果$miv[now]>left$则直接返回
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| #include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <queue>
#include <cmath>
#define ll long long
#define ri register int
using std::min;
using std::sqrt;
using std::max;
template <class T>inline void read(T &x){
x=0;int ne=0;char c;
while(!isdigit(c=getchar()))ne=c=='-';
x=c-48;
while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;
x=ne?-x:x;return ;
}
const int maxn=17;
const int inf=0x7fffffff;
int n,m,ans=inf,tmp;
int miv[maxn];
void dfs(int now,int val,int left,int r,int h){
if(!now){
if(!left)ans=min(ans,val);
return;
}
if(now<=0||left<=0)return ;
if(val+(left<<1)/r>ans||miv[now]>left)return;
for(ri i=r-1;i>=now;i--){
if(now==m)val=i*i;
tmp=min(left-miv[now-1]/(i*i),h-1);
for(ri j=tmp;j>=now;j--){
dfs(now-1,val+2*i*j,left-i*i*j,i,j);
}
}
return;
}
int main(){
read(n),read(m);
for(ri i=1;i<=m;i++)miv[i]=miv[i-1]+i*i*i;
int r=(int)sqrt(n/m),h=n/(m*m);
dfs(m,0,n,r,h);
if(ans==inf)puts("0");
else printf("%d\n",ans);
return 0;
}
|