自己想出这题的大佬蒟蒻在这儿%您了

我实在是太弱了，搜索这种辣鸡算法都不会（逃

这题真的是想了好久，每次都会T三个点，我以为我的剪枝已经堆了够多了，结果后来才知道是一个关键剪枝没想到OTZ

先贴代码

#include <bits/stdc++.h>

using namespace std;

#define rint register int

int n, m, ans = 99999999;

int ini1[20], ini2[20];

inline void init( void ){

	for( rint i = 1; i <= m; i++ ){

		ini1[i] = pow( i, 3 ) + ini1[i - 1];

		ini2[i] = 2 * i * i + ini2[i - 1];

	}

	return ;

}

inline void dfs( int nowv, int nows, int r, int h, int t ){

	if( t == 0 ){

		if( nows == n ) ans = min( ans, nowv );

		return ;

		//cout << 1;

	}

	if( nowv + ini2[t - 1] >= ans ) return ;

	//cout << 1;

	if( nows + ini1[t - 1] >= n ) return;

	//cout << 1;

	if( 2 * ( n - nows ) / r + nowv >= ans ) return ;

	for( rint i = r - 1; i >= t; i-- ){

		//cout << 1;

		if( t == m ) nowv = i * i;

		int hh = min( h - 1, ( n - nows - ini1[t - 1] ) / ( i * i ) );

		for( rint j = hh; j >= t; j-- ){

			//cout << t << endl;

			dfs( nowv + 2 * i * j, nows + i * i * j, i, j, t - 1 );

		}

	}

	return ;

}

int main( void ){

	scanf( "%d%d", &n, &m );

	init();

	int temp = sqrt( n );

	//for( int i = 1; i <= m; i++ ) cout << ini[i] << ' ';

	dfs( 0, 0, temp + 1, n + 1, m );

	if( ans == 99999999 ){

		cout << 0;

		return 0;

	}

	cout << ans;

	return 0;

}

看这输出的1就知道我错了多少次，结果发现把一个t打成了 $t - 1$ qwq

关键剪枝

if( 2 * ( n - nows ) / r + nowv >= ans ) return ;

这里详细推一下

1 到$ dep - 1$的体积为

$n - v = \sum_{k = 1}^{dep - 1}h[k] * r[k] ^ 2$

表面积为

$2\sum_{k = 1}^{dep - 1}h[k] *r[k] $

又臭又长警告

$\because2\sum_{k = 1}^{dep - 1}h[k] *r[k] = \frac{2}{r[dep]} * \sum_{k = 1}^{dep - 1}h[k]*r[k]*r[dep]\geqslant \frac{2}{r[dep]} *\sum_{k = 1}^{dep - 1}h[k]*r[k]^2\geqslant \frac{2(n - v)}{r[dep]}$

$\therefore$当$ \frac{2(n - v)}{r[dep]} + s \geqslant ans$时说明已经不是最优，即可return

这是对前$dep - 1$层侧面积的估计，很多人忽略了这一维度，其实，这一维度已经在我们预处理$ini$

（别激动，$init$删去$t$而已23333）时已经有所涉及，只是我们没有太在意而已

这告诉我们在设计剪枝条件的时候一定要全方面考虑

，每个维度都有所思考，尽可能到达上下界

return 0；//功德圆满

巴特西

题解 NOI1999【生日蛋糕】—— 洛谷

自己想出这题的大佬蒟蒻在这儿%您了

先贴代码

关键剪枝

最新文章

热门文章