题解 P1679 【神奇的四次方数】

# 将其转换为完全背包就好了 ``` #include<bits/stdc++.h> using namespace std; int s[200001],f[200001]; int m,n; int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) f[i]=1e8;//一定要刷新一下f数组 m=ceil(sqrt(sqrt(n))+1);//取一下上线 for(int i=1;i<=m;i++) s[i]=pow(i,4); for(int i=1;i<=m;i++) for(int j=s[i];j<=n;j++) f[j]=min(f[j],f[j-s[i]]+1);//完全背包动态转移方程 printf("%d\n",f[n]);//完美输出 } ```