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。代表有n个数。输出他们所有的不同关系 有多少种。
做法：开一个dp[ i ][ j ] i表示当前状态有几个字母，j表示当前状态有多少个不同的数 （也就是小于号+1）。
如：a < b < c a < c < b b < a < c b < c < a c < a < b
上面这些是有 有两个等于的状态，， 如果想再加一个不同于a，b，c的一个数d。 拿a < b < c 来说，可以有4种方法d<a<b<c或者a <d< b < c 或者 a<b<d<c 或者 a<b<c<d
而加和abc 某一个数相同的d拿拿a < b < c 来说 ，方法有3种d=a<b<c或者a <d=b < c 或者 a<b<d=c
再试试2推到3 或3推到4 的别的状态，
可以发现 从上一个状态 递归到 i状态，要乘上 i 状态 有多少不同数字，也就是乘上j 。
可以 有dp[ i ][ j ]= dp[ i – 1 ] [ j- 1 ]*j+dp[ i – 1 ] [ j ] *j
上面这表示加了一个不同的数上面的表示加了一个和原来数中某数相等的数
#include<stdio.h>#include<string.h>int dp[11][11]={0};//i 几个字母 j 有几个不相等的字母（i-等于号数）int main(){int n;dp[1][1]=1;int ans[11];for(int i=2;i<=10;i++){ans[i]=0;for(int j=1;j<=10;j++){dp[i][j]=dp[i-1][j-1]*j+dp[i-1][j]*j;//加一个小于号 加一个等于号ans[i]+=dp[i][j];}}while(scanf("%d",&n),n!=-1){printf("%d\n",ans[n]);}return 0;}
看自家总在期待,不知将来好歹,新乐吧总在不断等待,
