洛谷 P1679 神奇的四次方数

题目传送门

解题思路:

f[i]表示第i个数的组成方案数

AC代码:

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<cstring>
 5 
 6 using namespace std;
 7 
 8 int m,f[100001];
 9 
10 int main() {
11     memset(f,0x3f3f3f,sizeof(f));
12     scanf("%d",&m);
13     f[0] = 0;
14     for(int i = 1;i <= sqrt(sqrt(m)) + 10; i++){
15         int k = i * i * i * i;
16         for(int j = k;j <= m; j++) 
17             f[j] = min(f[j],f[j-k] + 1);
18     }
19     printf("%d",f[m]);    
20     return 0;
21 }