问题描述:

ZOJ Problem Set - 1475 
Ranklist 
Time Limit: 1 Second      Memory Limit: 32768 KB 
If n people take part in this contest, how many distinct ranklists there could be? Notice that some contestants may share the same rank. 

Input 
One n on each line, the number of participants ( 1 <= n <= 200 ). A negative value for n indicates the end of input. 

Output 
One number on each line, the number of distinct ranklists. 

Sample Input 
1 
2 
3 
-1 

Sample Output 
1 
3 
13 

Author: ZHOU, Qiang 

解题:

补充说下题目的意思,比如 n=3, 有三种情况

所以n=3时,有13种情况

所以当n比较大的时候情况很复杂,要设计好的算法

这题是dp+高精度, 递推式如下:

f(n) = g(n,1) + g(n,2) + ... + g(n,n)

其中, g(n,m) = g(n-1,m)*m + g(n-1,m-1)*m

f(n)表示n个人有多少种排列方法(即最终答案) g(n,m)表示n个人m个rank有多少种排列方法

上面第一个式子非常好理解, 相信不用我讲了

第二个式子是重点:

  1. 把g(n,m)对于其中某个人分类统计, 一是这个人与其他人共享rank, 二是这个人独占一个rank
  2. 对于第一类, 这个人与其他人共享rank, 排列数为g(n-1,m)*m, 即先拿掉这个人, 其他人排一下m个rank, 为g(n-1,m), 然后这个人加入到m个rank中的某个里面去
  3. 对于第二类, 这个人单独占一个rank(即没有其他人与这个人rank相同) 排列数为g(n-1,m-1)*m, 即先拿掉这个人, rank数也随之从m变为m-1, 其他人排一下, 为g(n-1,m-1), 然后这人插下队

式子大概是这样了, 计算时候注意一是要用高精度, 二是g(n,m)在m=1时, 等于1, 在m==n时, 等于n!, 其他时候, 等于那个递归式

#include <stdio.h> 
typedef long LongType; 
LongType result[201][201]; 
int N; 
LongType GetResult( int n, int m ); 

int main() 
{ 
    int i, j, k; 
    for ( i=0; i<201; ++i ) 
    { 
        for ( j=0; j<=i; ++j ) 
        { 
            result[i][j] = -1; 
            if ( 1 == j ) 
            { 
                result[i][j] = 1; 
            } 
            if ( i == j ) 
            { 
                result[i][j] = 1; 
                for ( k=2; k<=i; ++k ) 
                { 
                result[i][j] *= k; 
                } 
            } 
            if ( 0 ==i || 0==j ) 
                result[i][j] = 0; 
        } 
    } 

    LongType Sum; 
    while ( scanf("%d",&N) && N >0 ) 
    { 
        Sum = 0; 
        for ( k=1; k<=N; ++k ) 
        { 
            Sum += GetResult(N,k); 
        } 
        printf("%ld\n", Sum); 
    } 
    return 0; 
} 

LongType GetResult( int n, int m ) 
{ 
    if ( result[n][m] >= 0 ) 
    { 
        return result[n][m]; 
    } 
    else 
    { 
        return ( result[n][m] = GetResult(n-1,m)*m + GetResult(n-1,m-1)*m ); 
    } 
}