【SOJ-1865整数分割】最適化
817 ワード
#define N 501
ll d[N][N];
ll q(ll n, ll m)
{
if ((n < 1) || (m < 1)) return 0;
if (n == 1 || m == 1) return 1;
if (n < m) return q(n, n);
if (n == m) return q(n, m - 1) + 1;
return q(n, m - 1) + q(n - m, m);
}
int main()
{
memset(d, 0, sizeof(d));
ll i, j, k;
for (i = 1; i <= N; ++i) d[i][1] = d[1][i] = 1;
for (i = 0; i < N; ++i) {
for (j = 0; j < N; ++j) {
if (i < 1 || j < 1) d[i][j] = 0;
else if (i == 1 || j == 1) d[i][j] = 1;
else if (i < j) d[i][j] = d[i][i];
else if (i == j) d[i][j] = d[i][j - 1] + 1;
else {
d[i][j] = d[i][j - 1];
if (i - j > 0) d[i][j] += d[i - j][j];
}
}
}
ll n;
while (scanf("%lld", &n) == 1 && n) {
printf("%lld
", d[n][n]);
}
return 0;
}