【CF679B】Bear and Tower of Cubes

题意

对于一个数$x$，每次贪心地找到不小于剩下的数的最大的正整数的立方，减去这个数，并重复直至变成$0$，操作次数即为$x$的贡献。
在$[1,m]$中找到最大的贡献及对应的数最大值。

思路

其他题解给出了二分/$dfs$的做法，这里给出一种$DP$的做法。

将$m$分解为$\sum a_k^3{t}_k$，其实总共分解出来的数不多，考虑可以通过以下方式计算答案：枚举$k$，选取$a_k^3$的最后一个，不小于$a_k^3$的都保留，小于的都忽视，将$a_k^3$其拆开成最优的方案，与不小于$a_k^3$的贡献合起来。

接下来就考虑 $x^3$的贡献：将$x^3-1$分解，按照上面的方法计算，最后考虑$x^3$本身。

时间复杂度为$O(\sqrt[3]{m})$，答案最大也只有$18$，常数可以接受。

Code

#include
#define mid ((l+r)>>1)
#define hehe pair<long long,long long>
#define fir first
#define sec second
#define pb push_back
#define inf 1000000007
#define N 100005
using namespace std;
long long read()
{
	long long x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=(x<<1ll)+(x<<3ll)+ch-48,ch=getchar();
	return x*f;
}
void write(long long x)
{
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x/10);
	putchar(x%10+'0');
}
long long n,cb[N],lim;
vector<hehe>v;
hehe ans,f[N];
long long cube(long long x)
{
	return x*x*x;
}
long long ncb(long long x)
{
	return (long long)pow((double)x,(double)1/(double)3);
}
void solve(long long x)
{
	v.clear();
	for(long long t,d;x;)
	{
		t=ncb(x);
		while(cb[t]>x)t--;
		while(t<lim&&cb[t+1]<=x)t++;
		d=x/cb[t];
		v.pb({t,d});
		x-=d*cb[t];
	}
}
hehe dp(long long x)
{
	long long sum=0,total=0;
	hehe ans={0,0};
	for(auto &aut:v)
	{
		long long t=aut.fir,d=aut.sec;
		long long temp=sum+(d-1)+f[t].fir,size=total+cb[t]*(d-1)+f[t].sec;
		if(temp>ans.fir||(temp==ans.fir&&size>ans.sec))ans.fir=temp,ans.sec=size;
		sum+=d;
		total+=d*cb[t];
	}
	return ans;
}
int main()
{
	n=read();
	lim=ncb(n)+2;
	for(long long i=1;i<=lim;i++)
	{
		cb[i]=cube(i);
	}
	for(long long i=1;i<=lim;i++)
	{
		long long temp=cb[i]-1;
		solve(temp);
		f[i]=dp(temp);
		if(!f[i].fir)f[i].fir=i,f[i].sec=cb[i];
	}
	solve(n);
	ans=dp(n);
	printf("%lld %lld\n",ans.fir,ans.sec);
	return 0;
}

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81