序关系计数问题

序关系计数问题

时间： 1ms        内存：64M

描述：

用关系“＜”和“=”将3个数A、B和C依序排列时有13种不同的序关系：
A=B=C，A=B＜C，A＜B=C，A＜B＜C，A＜C＜B，A=C＜B，B＜A=C，B＜A＜C，B＜C＜A，
B=C＜A，C＜A=B，C＜A＜B，C＜B＜A。
将n 个数（1≤n≤50）依序排列时有多少种序关系。
计算出将n个数（1 ≤ n ≤ 50）依序排列时有多少种序关系。

输入：

输入数据只有一行，提供一个数n。

输出：

输出数据只有一个整数，表示找到的序关系数。

示例输入：

3

示例输出：

13

提示：

参考答案（内存最优[1696]）：

#include<cstdio>
#include<iostream>
using namespace std;
 
int main()
{
    long long int a[55][55];
    int n,i,j;
    while(cin>>n)
    {
    for(i=1;i<=n;i++)
        a[i][1]=1;
    a[1][2]=0;
    for(i=2;i<=n;i++)
    {
        for(j=2;j<=i;j++)
        {
            a[i][j]=j*(a[i-1][j-1]+a[i-1][j]);
        }
        a[i][i+1]=0;
    }
    long long int sum=0;
    for(i=1;i<=n;i++)
    {
        sum+=a[n][i];
    }
    printf("%lld\n",sum);
    }
    return 0;
}

参考答案（时间最优[0]）：

#include<cstdio>
#include<iostream>
using namespace std;
 
int main()
{
    long long int a[55][55];
    int n,i,j;
    while(cin>>n)
    {
    for(i=1;i<=n;i++)
        a[i][1]=1;
    a[1][2]=0;
    for(i=2;i<=n;i++)
    {
        for(j=2;j<=i;j++)
        {
            a[i][j]=j*(a[i-1][j-1]+a[i-1][j]);
        }
        a[i][i+1]=0;
    }
    long long int sum=0;
    for(i=1;i<=n;i++)
    {
        sum+=a[n][i];
    }
    printf("%lld\n",sum);
    }
    return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。