Permutation

Total Submit : 120    Accepted Submit : 47

Problem

Given a permutation of n elements (1, 2, ..., n): A = (a1, a2, ..., an). We define a sequence P(A)=(p1, p2, …, p(n-1)) where pi = 0 if A(i) > A(i+1) and pi = 1 if A(i) < A(i+1). Given a permutation B, find the number of all permutations C where P(C)=P(B) including the permutation B itself. 

Input

The input text file contains several tests, each on a separate line. The first number in the test is n followed by n numbers representing the permutation all of them separated by a single space. The last line in the input contatins only 0 and should not be processed. 

Output

The output should be written on the standard output. For each line in the input (excluding the last one, 0) you should write the result i.e. the number of the permutations having the same value for P(A) when given the permutation A. 

Sample input

2 1 2
4 1 3 2 4
0

Sample output

1
5

Problem Source

ZSUACM Team Member

========================邪恶的分割线=========================

题目的要求是按照升降序列来构造排列，可用构造一段三角波来描述这个过程。
三角波上的离散点的相对位置只表示相对大小，在还没添加所有的点之前，各个点并没有确定实际值。
对于当前点 V_i （i 从 0 开始），假设已经有 a 个点比它大，有 b 个点比它小，a + b = i 。（对于点 V₀ ， a₀ = 0 ， b₀ = 0 。）
如图 1 所示 ，小三角标示当前点，(a, b) = (1, 3) 表示有 1 个点高于其，有 3 个点低于其。注意任意两点的高度都不相等。
那么要添加下一个点时， 根据点之间的相对位置来划分，
(1) 上升有 a + 1 种位置，新点的 a' = 0 .. a ， b' = a+b+1 .. b+1 。如图 2 所示，每个小三角标示的点都可以作为添加的点。
(2) 下降有 b + 1 种位置，新点的 a' = a+b+1 .. a+1 ，b' = 0 .. b 。如图 3 所示。

因为 ( a_i , b_i) 可能会有重复的，所以只要记录其数目即可。
因为 a_i + b_i = i ，所以只要记录 b_i 即可。
因此使用一个二维数组 cnt [ ] [ ]，行标 i 表示第 i 个点，列标 j 表示低于第 i 个点的点的数目，cnt [ i ] [ j ] 表示可行的情况数目。

例如升降序列是 “降升降” （n = 4） ，那么构造所有的三角波，构造完成后根据点的高度来给它赋值 1 .. n 。

生成的 5 个排列是 4132 ， 4231，2143， 3142， 3241 。

过程中产生的 (a, b)，如对于 V₃ ， (3, 0) 出现两次，则 cnt [3] [0] = 2。
点 (a, b)
0    (0, 0)
1    (1, 0)
2    (0, 2),(1, 1)
3    (3, 0),(2, 1),(1, 2)   (3, 0),(3, 1)
和上面的图顺序有点不一样，当时没在图上标示好，将就点吧 o(∩_∩)o...

如果上升，那么 cnt [i - 1] [j] 对应的位置都能够产生 cnt [i] [j+1..i] 对应的某个位置。
如果下降，那么 cnt [i - 1] [j] 对应的位置都能够产生 cnt [i] [0..j] 对应的某个位置。
代码如下：
（递推法分析，然后动态规划实现，时间复杂度是 O (n³) 的）

#include <cstdio>
#include <memory.h>
using namespace std;

const int N = 100;
long long cnt [N] [N];
int seq [N];
int n;

void f ()
...{
    memset (cnt, 0, sizeof (cnt));
    cnt [0] [0] = 1;
    int i, j, k;
    for (i = 0; i < n; i ++)
        ...{
        scanf ("%d", &seq [i]);
        }
    for (i = n - 1; i; i --)
        ...{
        seq [i] = (seq [i] > seq [i - 1] ? 1 : 0);
        }
    for (i = 1; i < n; i ++)
        ...{
        for (j = 0; j <= i; j ++)
            ...{
            if (seq [i])
                ...{
                // 如果上升则 cnt [i - 1] [j] 对应的位置都能够产生 cnt [i] [j+1..i] 对应的某个位置
                for (k = j + 1; k <= i; k ++)
                    ...{
                    cnt [i] [k] += cnt [i - 1] [j];
                    }
                } else    ...{
                    // 如果下降则 cnt [i - 1] [j] 对应的位置都能够产生 cnt [i] [0..j] 对应的某个位置
                    for (k = 0; k <= j; k ++)
                        ...{
                        cnt [i] [k] += cnt [i - 1] [j];
                        }
                    }
            }
        }
    long long sum = 0;
    for (i = 0;  i < n; i ++)
        ...{
        sum += cnt [n - 1] [i];
        }
    printf ("%lld ", sum);
}

int main ()
...{
    while (scanf ("%d", &n), n)
        ...{
        f ();
        }
    return 0;
}

提交结果：

PS：这次报告写得不怎么样。。表达能力不高，见笑了。。
今天晚上吃了月饼，呵呵。。