小水题再来一发

给定一个正整数n<=1e4，求将n写成若干个正整数立方和的方法数

 

典型的多阶段模型

f[i][j]表示当前用到1~i的数，累计和为j的方案数。

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 using namespace std; 6  7 typedef long long LL; 8 LL f[30][10010]; 9 10 int main()11 {12     //freopen("a.in","r",stdin);13     memset(f,0,sizeof(f));14     f[0][0]=1;15     for(int i=1;i<=21;i++)16         for(int j=0;j<=10000;j++)17         {18             f[i][j]=f[i-1][j];19             if(j>=i*i*i) f[i][j]+=f[i][j-i*i*i];20         }21     int n;22     while(scanf("%d",&n)!=EOF)23     {24         printf("%lld\n",f[21][n]);25     }26     27     return 0;28 }