poj 1221 Unimodal Palindromic Decompositions(DP)

Description

A sequence of positive integers is Palindromic if it reads the same forward and backward. For example:
23 11 15 1 37 37 1 15 11 23
1 1 2 3 4 7 7 10 7 7 4 3 2 1 1
A Palindromic sequence is Unimodal Palindromic if the values do not decrease up to the middle value and then (since the sequence is palindromic) do not increase from the middle to the end For example, the first example sequence above is NOT Unimodal Palindromic while the second example is.
A Unimodal Palindromic sequence is a Unimodal Palindromic Decomposition of an integer N, if the sum of the integers in the sequence is N. For example, all of the Unimodal Palindromic Decompositions of the first few integers are given below:
1: (1)
2: (2), (1 1)
3: (3), (1 1 1)
4: (4), (1 2 1), (2 2), (1 1 1 1)
5: (5), (1 3 1), (1 1 1 1 1)
6: (6), (1 4 1), (2 2 2), (1 1 2 1 1), (3 3),
(1 2 2 1), ( 1 1 1 1 1 1)
7: (7), (1 5 1), (2 3 2), (1 1 3 1 1), (1 1 1 1 1 1 1)
8: (8), (1 6 1), (2 4 2), (1 1 4 1 1), (1 2 2 2 1),
(1 1 1 2 1 1 1), ( 4 4), (1 3 3 1), (2 2 2 2),
(1 1 2 2 1 1), (1 1 1 1 1 1 1 1)

Write a program, which computes the number of Unimodal Palindromic Decompositions of an integer.

Input

Input consists of a sequence of positive integers, one per line ending with a 0 (zero) indicating the end.

Output

For each input value except the last, the output is a line containing the input value followed by a space, then the number of Unimodal Palindromic Decompositions of the input value. See the example on the next 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

解题思路

题意：

    给一个正整数，求出它的Unimodal Palindromic的个数，所谓的Unimodal Palindromic就是一系列数，单调递增再递减，并且第一个和最后一个数相同，第二个跟倒数第二个数相同，即第i个跟第n-i+1个数相同。

 

思路：

    完全没思路，感觉跟DP扯不上半点关系，后来网上找了些解题报告研究一下午才搞出来。这个题做得很猥琐。

    把它的Unimodal Palindromic分成两部分：一部分是最小数是j的，就是第一个跟最后一个数等于j的有几个；第二部分是最小数大于j的，可以是j+1，j+2…..的有几个。

    s[i][j]表示和为i，最小数是j的序列的个数。那么第一部分就是s[i-j*2][j],

意思就是和为去掉了首尾两个数后的和，最小数是j；第二部分就是s[i][j+1].最小数大于j的情况的个数。状态转移方程：

s[i][j] = s[i-2*j] + s[i][j+1]

初始化：

①．s[0][j]初始值1.因为当需要调用s[0][j]时，表示拆成了两个相同的数。有一个

②．S[i][j]（i）初始值0，不可能的情况

③．S[i][j] (i>=j >i/2) 初始值1，j>i/2时所有s[i][j]都是1，那个就是i本身。

源程序

 

#include <stdio.h>
#include <string.h>
#include <conio.h>
#define N 300

int main()
{
    int i, j;
    int n;
    unsigned int s[N][N];
    freopen("in.txt", "r", stdin);
    memset(s, 0, sizeof(s));
    
    for(i=1; i<N; i++)
        s[0][i] = 1;
    for(i=1; i<N; i++)
        for(j=i/2+1; j<=i; j++)
            s[i][j] = 1;
    for(i=2; i<N; i++)
        for(j=i/2; j>0; j--)
            s[i][j] = s[i-2*j][j]+s[i][j+1];

    while(scanf("%d", &n) && n)
    {
        printf("%d %u\n",n, s[n][1]);
    }

    getch();
    return 0;
}