ural 1142. Relations

1142. Relations

Time limit: 1.0 second
Memory limit: 64 MB

Background

Consider a specific set of comparable objects. Between two objects a and b, there exits one of the following three classified relations:

a = b
a < b
b < a

Because relation '=' is symmetric, it is not repeated above.

So, with 3 objects (a, b, c), there can exist 13 classified relations:

a = b = c a = b < c c < a = b a < b = c
b = c < a a = c < b b < a = c a < b < c
a < c < b b < a < c b < c < a c < a < b
c < b < a

Problem

Given N, determine the number of different classified relations between N objects.

Input

Includes many integers N (in the range from 2 to 10), each number on one line. Ends with −1.

Output

For each N of input, print the number of classified relations found, each number on one line.

Sample

input	output
2 3 -1	3 13

Tags: none (hide tags for unsolved problems)

Difficulty: 144

题意：计算N个数的大小比较关系的可能情况的总数。

分析：n个数，中间插入一些小于号。其余位置用等号。

等号相连的数的位置没有区别。

问题相当于问将n个数分为几个部分有多少种办法。

dp即可

dp[i][j]表示i个数，分为j组的方案数。

dp[i][j] += dp[i - 1][j] * j 表示第i个数有j中选择加入。

dp[i][j] += dp[i-1][j-1] * j 表示第i个数自立门户，然后这个新的部分插入其他j-1个已经确立大小关系的部分的方法有j种

 /**

 Create By yzx - stupidboy

 */

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <cmath>

 #include <deque>

 #include <vector>

 #include <queue>

 #include <iostream>

 #include <algorithm>

 #include <map>

 #include <set>

 #include <ctime>

 #include <iomanip>

 using namespace std;

 typedef long long LL;

 typedef double DB;

 #define MIT (2147483647)

 #define INF (1000000001)

 #define MLL (1000000000000000001LL)

 #define sz(x) ((int) (x).size())

 #define clr(x, y) memset(x, y, sizeof(x))

 #define puf push_front

 #define pub push_back

 #define pof pop_front

 #define pob pop_back

 #define ft first

 #define sd second

 #define mk make_pair

 inline int Getint()

 {

     int Ret = ;

     char Ch = ' ';

     bool Flag = ;

     while(!(Ch >= '' && Ch <= ''))

     {

         if(Ch == '-') Flag ^= ;

         Ch = getchar();

     }

     while(Ch >= '' && Ch <= '')

     {

         Ret = Ret *  + Ch - '';

         Ch = getchar();

     }

     return Flag ? -Ret : Ret;

 }

 const int N = ;

 int n;

 int dp[N][N], ans[N];

 inline void Init()

 {

     dp[][] = ;

     for(int i = ; i <= ; i++)

         for(int j = ; j <= i; j++)

             dp[i][j] = dp[i - ][j] * j + dp[i - ][j - ] * j;

     for(int i = ; i <= ; i++)

         for(int j = ; j <= i; j++)

             ans[i] += dp[i][j];

 }

 inline void Solve();

 inline void Input()

 {

     Init();

     while(scanf("%d", &n) == )

     {

         if(n == -) return;

         Solve();

     }

 }

 inline void Solve()

 {

     printf("%d\n", ans[n]);

 }

 int main()

 {

     freopen("a.in", "r", stdin);

     Input();

     //Solve();

     return ;

 }

秒客网