POJ 1121-UNIMODAL PALINE DROMIC DECOMPOSITIONSダイナミック企画

タイトルのソース:http://poj.org/problem?id=1221
問題解決報告:
この問題は与えられた数字nを求めています.nを求めてどれぐらいの種類のunimodal palindromic decompationsに分解できますか?つまり、まず文字列の性質を満足させてから、前半はインクリメント順です.
私の解法は:
f[n][k]を取って、対nを代表して、文列の第一個数>=kを取り戻す時のpalindromicを表します. decompationsの種類.
f[n][k]に対して、まずf'[n][k]代表回文列の最初の数を計算します.kは、Palindromic decompationsの種類です.
f'[n][k]=f[n-2**k]があり、そのうちの1<=k==n/2
f[n][k]=f'[n]+f'[n]、[n]、[k＋1]+f[n]
最後に求められるのはf[n][1]です.

#include <iostream>
using namespace std;

#define N 300

long long *f[N];  //    ， long long,     WA    。

void compute(int n);

long long get(int n, int k) {
	if (f[n][k]!=0)
		return f[n][k];
	else
		compute(n);
	return f[n][k];
}

void compute(int n) {
	if (f[n][n] != 0) {
		return;
	}
	for (int j = 1; j<=n/2;j++) {
		if (n-2*j >= j) {
			f[n][j] += get(n-2*j,j);
		}
	}
	if ((n/2)*2 == n)
		f[n][n/2] += 1;
	f[n][n]=1;
	for (int j=n-1; j>=1;j--) {
		f[n][j] += f[n][j+1];
	}
}



int main()
{
	for (int i =0 ; i< N; i++) {
		f[i] = new long long[i+1];
		for (int j=0;j<=i;j++) {
			f[i][j] = 0;
		}
	}

	int n;
	cin >> n;
	f[1][1]=1;
	while(n!=0)
	{
		compute(n);
		cout << n << " " << f[n][1] << endl;
		cin >> n;
	}
}

付録:
Description
A sequence of positive integers is Palindromic if it reads the same forward and backward.For example: 
23 11 11 15 1 37 1 15 11 23 
1 2 3 4 7 7 7 7 7 4 2 1 
A Palindromic sequence is Unicode Palindromic if the values do not decrease up to the middle value and then(since the sequence is palindromic)do increase from the middle the end Fored Foreample,the 
A Uniimodal Palindromic sequence is a Uniimodal Palindromic Decompsition of an integer N,if the sum of the integers in the sequence is N.For example,all of the Unimodal Palindromic Decompation Decompations Decompations of the of the firs bers Bers Bers Berse Berse Berse Berse Berse Berse Berse Berse Berse Berse Berse Be 
1:(1) 
2:(2)、(1) 
3:(3)、(1) 
4:(4)、(1 2)、(2)、(1 1 1) 
5:(5)(1 3),(1 1 1 1 1 1) 
6:(6)、(1 4 1)、(2)、(1 2 1 2 1)1)、(3) 
(1 2 2 1)、(1 1 1 1 1 1 1 1) 
7:(7)、(1 5 1)、(2 3)、(1 3 1 1 1 1 1)(1)1)1 
8:(8)、(1 6 1)、(2 4)、(1 4 1,1)、(1 2,2,1) 
(1 1 1 1 1 2 1 1)、(4)、(1 3 1)、(2 2 2)、 
(1 1 1 2 1)、(1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1) 
Write a program,which computes the number of Unimodal Palindromic Decompsitions of an integer. 
Input
Input consists of a sequence of positive integers、one per line ending with a 0(ゼロ)indicating the end. 
Output
For each input value except the last,the out put is a line containing the input value followed by a space,the n the number of Unimodal Palindromic Decompsitions of the input value.See the the ext.ext.page.page.page. 
Sample Input

2
3
4
5
6
7
8
10
23
24
131
213
92
0

Sample Output

2 2
3 2
4 4
5 3
6 7
7 5
8 11
10 17
23 104
24 199
131 5010688
213 1055852590
92 331143