排队问题
有24个高低不同的同学，现要排成三行，每一行从左到右由低到高，每一列从前到后也是由低到高。有多少种排法？ 应该是3192727797 每行人数相同还是允许不同？ northwolves 发表于 2020-10-28 10:22每行人数相同还是允许不同？
每行人数相同啊
mathe 发表于 2020-10-28 09:04
应该是3192727797
除了暴力枚举法，还有什么简单算法 动态规划 将24个人依次从低到高排好位置，按前k个人使用掉的位置集合进行分类(不区分每个人的具体位置)，递推各分类的人数即可 mathe 发表于 2020-10-28 12:03
将24个人依次从低到高排好位置，按前k个人使用掉的位置集合进行分类(不区分每个人的具体位置)，递推各分类 ...
能写出DP公式吗？
#include <map>
using namespace std;
typedef struct _PC{
char cnt;
bool operator<(const struct _PC& x)const{
int i;
for(i=0;i<3;i++){
if(cnt<x.cnt)return true;
if(cnt>x.cnt)return false;
}
return false;
}
bool operator==(const struct _PC& x)const{
int i;
for(i=0;i<3;i++){
if(cnt!=x.cnt)return false;
}
return true;
}
}PC;
typedef map<PC, long> PCMAP;
PCMAP pcmap0, pcmap1;
void add_data(PCMAP *next_map, const PC& data, long count)
{
PCMAP::iterator it = next_map->find(data);
if(it==next_map->end()){
next_map->insert(std::make_pair(data, count));
}else{
it->second+=count;
if(it->second<0L){
printf("overflow\n");
}
}
}
#define N 8
int main()
{
PCMAP *prev, *next, *tmp;
int i;
prev=&pcmap0;
next=&pcmap1;
PC pc;
pc.cnt=1;pc.cnt=pc.cnt=0;
prev->insert(std::make_pair(pc, 1L));
for(i=2;i<=3*N;i++){
next->clear();
PCMAP::iterator it;
for(it=prev->begin();it!=prev->end();++it){
const PC& orig = it->first;
PC update = orig;
if(update.cnt<N){
update.cnt++;
add_data(next, update, it->second);
}
if(orig.cnt>orig.cnt){
update=orig;
update.cnt++;
add_data(next,update, it->second);
}
if(orig.cnt>orig.cnt){
update=orig;
update.cnt++;
add_data(next,update, it->second);
}
}
tmp=prev;
prev=next;
next=tmp;
}
long sum = 0;
PCMAP::iterator it;
for(it=prev->begin();it!=prev->end();++it){ sum+=it->second;}
printf("Total %ld\n",sum);
}
进而推到一般情况，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)=?
页:
[1]
2