pku 1221 單峰回文

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <iostream>

#include <string>

using namespace std;

#define N 500

__int64 opt[N+1][N+1];

//狀态轉移: f[i][j]為數i由最小元素為j的單峰回文組成.

//則有: f[i][j] = f[i][j+1] + f[i-2*j][j] (i-2*j>=j, i-2*j == 0)

//不說具體了, 你懂的.

int main()

{

for(int i = 1; i <= N; ++i)

opt[i][i] = 1;

for(int i = 2; i <= N; ++i)

for(int j = i-1; j >= 1; --j)

{

opt[i][j] = opt[i][j+1];

if(i-2*j >= j)

opt[i][j] += opt[i-2*j][j];

else if(i-2*j == 0)

opt[i][j] += 1;

}

int n;

while(scanf("%d", &n) && n)

printf("%d %I64d/n", n, opt[n][1]);

return 0;

}