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;

}