本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-11 00:16:54

题意

删除一个整数 $x$ 要花费 $x$ 的代价，并会产生 $\lfloor \frac{x}{2}\rfloor$ 和 $\lceil \frac{x}{2} \rceil$ 两个新数。现在有一个整数 $N$，求使最后剩下的数均小于 $2$ 需花费的代价。

思路

若设 $f_x$ 为处理 $x$ 需花费的代价，令 $a=\lfloor \frac{x}{2}\rfloor,b=\lceil \frac{x}{2} \rceil$，则据题意易得 $f_1=0,f_x=f_a+f_b+x(x\ge2)$。

显然可以用递归解决。

但是直接暴力递归时间会炸。

所以考虑使用记忆化搜索，用map记录下每个数所需的代价。

时间复杂度应为 $O(\log N)$ 级别，可以通过本题。

代码

#include<iostream>
#include<map>
#define int long long
using namespace std;
int read()
{
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){ if(ch=='-') w=-1; if(ch==EOF) return 0; ch=getchar();}
	while(ch>='0'&&ch<='9'){ s=s*10+ch-'0'; ch=getchar();}
	return s*w;
}
int n,ans=0;
map <int,int> ma;
int erase(int x)
{
	if(x<2)
		return 0;
	if(!ma.count(x))
	{
		if(x%2==0)
			ma[x]=erase(x\/2)*2+x;
		else
			ma[x]=erase(x\/2)+erase(x\/2+1)+x;\/\/简单分类讨论+记忆化
	}
	return ma[x];
}
signed main()
{
	n=read();
	cout<<erase(n);
	return 0;
}