題意：
? ? ? 給你一個n(<=10000),問他如果由立方數之和組成，那么有多少種方法？
思路：?
? ? ? 一個地推公式，d[i][j] 表示用不大于i的數字去組合j這個數字有多少種方法，因為n<=10000所以i最大是21，最后答案就是d[21][n],地推公式是
d[i][j] = d[i-1][j] + d[i][j-i*i*i];
可以這樣理解，d[i-1][j]好說，就是不用當前這個數，d[i][j-i*i*i]表示的是用i，同時
for(i = j ;j <= n ;j ++)正著跑還能是的i用多次，想起了01和完全背包。


#include<stdio.h>
#include<string.h>


long long d[23][10005];
? ? ?
void solve()
{
? ?for(int i = 1 ;i <= 10000 ;i ++)
? ?d[1][i] = 1;
? ?for(int i = 1 ;i <= 21 ;i ++)
? ?d[i][0] = 1;
? ?for(int i = 2 ;i <= 21 ;i ++)
? ?for(int j = 1 ;j <= 10000 ;j ++)
? ?{
? ? ? d[i][j] = d[i-1][j];
? ? ? if(j - i * i * i >= 0)
? ? ? d[i][j] += d[i][j-i*i*i];
? ?}
} ? ??


int main()
{
? ?int n;
? ?solve();
? ?while(~scanf("%d" ,&n))
? ?{
? ? ? printf("%lld\n" ,d[21][n]);
? ?}
? ?return 0;
}

總結

以上是生活随笔為你收集整理的UVA11137(立方数之和)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。