ABC340C 题解

KSCD_ · 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;
}