思路

先枚举出 \(n\)以内的4次方数
然后dp.

代码

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define min(x,y) (x<y?x:y)
using namespace std;
inline void read(int &x) {
	x=0;
	short flag=1;
	char c = getchar();
	while(c<'0'||c>'9') {
		if(c=='-')flag=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9') {
		x=(x << 3)+ (x << 1)+(c ^ 48);
		c=getchar();
	}
	x*=flag;
}
inline void write(int x) {
	if(x<0) {
		putchar('-');
		x=-x;
	}
	if(x>9)
		write(x/10);
	putchar(x%10+'0');
}
const int MAXN=200010;
int s[MAXN],f[MAXN];
int m;
int main()
{
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
        f[i]=1e8;
    int n=ceil(sqrt(sqrt(m))+1);
    for(int i=1;i<=n;i++)
        s[i]=i*i*i*i;
    for(int i=1;i<=n;i++)
        for(int j=s[i];j<=m;j++)
            f[j]=min(f[j],f[j-s[i]]+1);
    printf("%d\n",f[m]);
}