排队问题

aimisiyou

有24个高低不同的同学，现要排成三行，每一行从左到右由低到高，每一列从前到后也是由低到高。有多少种排法？

mathe

应该是3192727797

northwolves

每行人数相同还是允许不同？

aimisiyou

northwolves 发表于 2020-10-28 10:22
每行人数相同还是允许不同？

每行人数相同啊

aimisiyou

mathe 发表于 2020-10-28 09:04
应该是3192727797

除了暴力枚举法，还有什么简单算法

mathe

动态规划

mathe

将24个人依次从低到高排好位置，按前k个人使用掉的位置集合进行分类(不区分每个人的具体位置)，递推各分类的人数即可

aimisiyou

mathe 发表于 2020-10-28 12:03
将24个人依次从低到高排好位置，按前k个人使用掉的位置集合进行分类(不区分每个人的具体位置)，递推各分类 ...

能写出DP公式吗？

mathe

1. 
   
2. #include <map>
   
3. using namespace std;
   
4. typedef struct _PC{
   
5.     char cnt[3];
   
6.     bool operator<(const struct _PC& x)const{
   
7.         int i;
   
8.         for(i=0;i<3;i++){
   
9.             if(cnt[i]<x.cnt[i])return true;
   
10.             if(cnt[i]>x.cnt[i])return false;
    
11.         }
    
12.         return false;
    
13.     }
    
14.     bool operator==(const struct _PC& x)const{
    
15.         int i;
    
16.         for(i=0;i<3;i++){
    
17.             if(cnt[i]!=x.cnt[i])return false;
    
18.         }
    
19.         return true;
    
20.     }
    
21. }PC;
    
22. 
    
23. typedef map<PC, long> PCMAP;
    
24. 
    
25. PCMAP pcmap0, pcmap1;
    
26. void add_data(PCMAP *next_map, const PC& data, long count)
    
27. {
    
28.     PCMAP::iterator it = next_map->find(data);
    
29.     if(it==next_map->end()){
    
30.         next_map->insert(std::make_pair(data, count));
    
31.     }else{
    
32.         it->second+=count;
    
33.         if(it->second<0L){
    
34.                 printf("overflow\n");
    
35.         }
    
36.     }
    
37. }
    
38. 
    
39. #define N 8
    
40. int main()
    
41. {
    
42.     PCMAP *prev, *next, *tmp;
    
43.     int i;
    
44.     prev=&pcmap0;
    
45.     next=&pcmap1;
    
46.     PC pc;
    
47.     pc.cnt[0]=1;pc.cnt[1]=pc.cnt[2]=0;
    
48.     prev->insert(std::make_pair(pc, 1L));
    
49.     for(i=2;i<=3*N;i++){
    
50.         next->clear();
    
51.         PCMAP::iterator it;
    
52.         for(it=prev->begin();it!=prev->end();++it){
    
53.             const PC& orig = it->first;
    
54.             PC update = orig;
    
55.             if(update.cnt[0]<N){
    
56.                update.cnt[0]++;
    
57.                add_data(next, update, it->second);
    
58.             }
    
59.             if(orig.cnt[0]>orig.cnt[1]){
    
60.                 update=orig;
    
61.                 update.cnt[1]++;
    
62.                 add_data(next,update, it->second);
    
63.             }
    
64.             if(orig.cnt[1]>orig.cnt[2]){
    
65.                 update=orig;
    
66.                 update.cnt[2]++;
    
67.                 add_data(next,update, it->second);
    
68.             }
    
69.         }
    
70.         tmp=prev;
    
71.         prev=next;
    
72.         next=tmp;
    
73.     }
    
74.     long sum = 0;
    
75.     PCMAP::iterator it;
    
76.     for(it=prev->begin();it!=prev->end();++it){ sum+=it->second;}
    
77.     printf("Total %ld\n",sum);
    
78. }
    
79. 
    

复制代码

aimisiyou

进而推到一般情况，m行n列，求通项公式F(m,n).显然有F(m,n)=F(n,m)。F(1,n)=F(n,1)=1,F(2,n)=F(n,2)=C(2n,n)/(n+1)  (卡特兰数)
F(3,n)=?
F(m,n)=?