题目链接：?space=1&num=1142
1142. Relations
Time limit: 1.0 secondMemory limit: 64 MB
Background
Consider a specific set of comparable objects. Between two objectsaandb, there exits one of the following three classified relations:
a=ba<bb<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 = cb = c < a a = c < b b < a = c a < b < ca < c < b b < a < c b < c < a c < a < bc < b < a
Problem
GivenN, determine the number of different classified relations betweenNobjects.
Input
Includes many integersN(in the range from 2 to 10), each number on one line. Ends with 1.
Output
For eachNof input, print the number of classified relations found, each number on one line.
Sample
inputoutput
23-1313
题意：用'<‘符号和’=’符号来表示 n 个数字，等号之间可以看成是一个整体，
求方案数？
PS:
dp[i][j]：表示将i个数分成j个有序集合的方案数1、如果将第i个数新建一个集合插进某个位置，方案数为：dp[i-1][j-1]*j2、如果将第i个数插进原有的集合，，方案数为：dp[i-1][j]*j
所以：dp[i][j]=dp[i-1][j-1]*j + dp[i-1][j]*j
代码如下：
#include <cstdio>#include <cstring>int dp[147][147];int ans[47];//dp[i][j] = dp[i-1][j]*j + dp[i-1][j-1]*j;void init(){memset(ans, 0,sizeof(ans));dp[1][0] = 0;dp[1][1] = 1;for(int i = 2; i <= 10; i++){for(int j = 1; j <= i; j++){dp[i][j] = dp[i-1][j]*j + dp[i-1][j-1]*j;ans[i] += dp[i][j];}}}int main(){int n;while(~scanf("%d",&n)){if(n == -1)break;init();printf("%d\n",ans[n]);}return 0;}/*2345678910*/
世上没有绝望的处境，只有对处境绝望的人。
