ZOJ 2284 Inversion Number

求N排列中逆序数对为K对的个数。

需要一个小技巧。一个形为{2,1,5,3,4}的5-排列,可以转化为一个{0,1,0,1,1}的排列。这里每个元素Ai表示i前逆序数的对数。易证明两者一一对应。

这样就把问题转化为求åAi=K,Ai<=i的排列个数。设F(i,j)表示前i个数之和达到j的排列个数,DP打表即得解。

 1#include <cstdio>
 2#include <string>
 3
 4const int MAXN = 20;
 5
 6int m[21][201][MAXN], N, K;
 7
 8void add ( int x1, int m1, int x2, int m2 )
 9{
10    int i;
11    for ( i = 0; i < MAXN; i ++ )
12    {
13        m[x1][m1][i] += m[x2][m2][i];
14    }

15    int c = 0;
16    for ( i = 0; i < MAXN; i ++ )
17    {
18        int t = c + m[x1][m1][i];
19        c = t / 10;
20        m[x1][m1][i] = t % 10;
21    }

22}

23
24void print ( int x1, int m1 )
25{
26    //printf ( "$%d\n", m[x1][m1][1] );
27    int i;
28    for ( i = MAXN - 1; m[x1][m1][i] == 0 && i >= 0; i -- )
29        ;
30    if ( i == -1 )
31    {
32        printf ( "0" );
33    }

34    else
35    {
36        for ( ; i >= 0; i -- )
37        {
38            printf ( "%d", m[x1][m1][i] );
39        }

40    }

41}

42
43void dp ()
44{
45    memset ( m, 0, sizeof ( m ) );
46    int i, j, k;
47    m[0][0][0= 1;
48    for ( i = 1; i < 20; i ++ )
49    {
50        for ( j = 0; j < 200; j ++ )
51        {
52            for ( k = 0; k <= i && j - k >= 0; k ++ )
53            {
54                add ( i, j, i - 1, j - k );
55            }

56        }

57    }

58    //pt ();
59}

60
61int main ()
62{
63    //freopen ( "in.txt", "r", stdin );
64    dp ();
65    while ( scanf ( "%d %d"&N, &K ) )
66    {
67        if ( N == 0 && K == 0 )
68        {
69            break;
70        }

71        print ( N - 1, K );
72        printf ( "\n" );
73    }

74    return 0;
75}

posted on 2008-02-04 15:01 杜仲当归 阅读(560) 评论(0)  编辑 收藏 引用 所属分类: 动态规划

只有注册用户登录后才能发表评论。

导航

<2008年2月>
272829303112
3456789
10111213141516
17181920212223
2425262728291
2345678

统计

常用链接

留言簿(1)

随笔分类

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜