CodeForces 679B(Bear and Tower of Cubes)

题意:Limak要垒一座由立方体垒成的塔。现有无穷多个不同棱长(a>=1)的立方体。要求:1、塔的体积为X(X<=m).2、在小于X的前提下,每次都选体积最大的砖块。3、在砖块数最多的前提下,使X尽可能大。求最终垒成塔所用的最大砖块数和塔可能的最大体积(在砖块数最多的前提下)。

思路:首先找到一个体积最大的砖块first_block( a3 ≤ m)。现在first_block的a有两种选择,a和a-1。

设此时剩余可使用体积为mm。

1、若first_block的棱长为a,则mm= m - a3.(第39行)(将此情况递归,最终将可能的num和current的最大值记录在best中)

2、若first_block的棱长为a-1,则mm= a3 - 1 - (a - 1)3(第41行)

PS:

1、first_block的棱长不选a-2,甚至更小棱长的原因:因为立方体的体积:1,8,27,64,125……显然m-(a-1)^3>(a-2)^3,

且a越大,这种情况越明显。所以选完一个(a-1)为棱长的立方体后,必有剩余体积可再选a-2的,所以只需选a-1的。

2、第33行比较顺序的原因:题意中首先要求砖块数最大,其次X尽可能大。(current累加到最终等于X)

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<set>
#include<cctype>
#include<vector>
#include<stack>
#include<map>
#include<queue>
#include<deque>
#include<list>
const int INF = 0x7f7f7f7f;
const double PI=acos(1.0);
typedef long long ll;
typedef unsigned long long llu;
const int MAXN= + ;
using namespace std;
ll p(ll x)//求边长为x的立方体的体积
{
return x*x*x;
}
pair<ll, ll> best;
void rec(ll m, ll num, ll current)//num砖块总数,current目前塔的总体积
{
if(m==)
{
best=max(best, make_pair(num, current));//make_pair()可生成一个pair对象,比较时先比较第一个值,若第一个值相同,再比较第二个值
return;
}
ll x = ;
while(p(x+)<=m)//得到小于等于m的最大体积的立方体的边长
++x;
rec(m-p(x), num+, current+p(x));
if(x - >= )
rec(p(x)--p(x-), num+, current+p(x-));
}
int main()
{
ll m;
scanf("%lld",&m);
rec(m,,);
printf("%lld %lld\n",best.first,best.second);
return ;
}
 
上一篇:Python3之Django连接mysql数据库


下一篇:django 连接MYSQL时,数据迁移时报:django.db.utils.InternalError: (1366, "Incorrect string value: '\\xE9\\x97\\xAE\\xE9\\xA2\\x98' for column 'name' at row 5")