【UVA】11137-Ingenuous Cubrency

DP問題は、時計を打つ必要があります.
dp[i][j]は、iを超えない大きさの数字を用いてjを構成する方法を表す.
状態方程式はdp[i][j]=d[i-1][j]+sum{dp[i-1][j-k*i*i*i]}である.
14327705
11137
Ingenuous Cubrency
Accepted
C++
0.049
2014-10-09 10:20:48

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int maxn = 11111;
const int maxd = 10000;
LL dp[40][maxn];
void List(){
    memset(dp,0,sizeof(dp));
    for(int i = 1 ; i <= maxd ; i++) dp[1][i] = 1;
    for(int i = 2 ; i * i * i <= maxd ; i ++){
        for(int j = 1; j <= maxd ; j ++){
            dp[i][j] += dp[i - 1][j];
            for(int k = 1; ; k ++){
                if(j - k * i * i * i > 0)
                    dp[i][j] += dp[i - 1][j - k * i * i * i];
                else if(j - k * i * i * i == 0)
                    dp[i][j] ++;
                else
                    break;
            }
        }
    }
}
int main(){
    List();
    int n,k;
    for(k = 1; k * k * k <= maxd ; k ++);
    while(scanf("%d",&n) != EOF){
        printf("%lld
",dp[k - 1][n]);
    }
    return 0;
}