>
算法与数据结构 算法与数据结构 11684成员

一个组合计数问题

Earthson 2010-07-25
问题参见joj 2419:http://acm.jlu.edu.cn/joj/showproblem.php?pid=2419
其实就是格子路径问题,但是有几点要注意
1、不能跑到对角线的上面^^
2、允许对角线路径
3、路径不能有往左或者往下的趋势,只能是按照向量(0,1) (1,0)(1,1)步进
4、注意到规模n达到了1000,这个导致从(0,0)到(n,n)的路径数达到近800位整数
。。。
以下是本人一个超时的程序,dp基于递推式
d[i][j]=d[i-1][j]+d[i][j-1]+d[i-1][j-1]
i==0 => d[i][j]=1
i<j => d[i][j]=0


#include <cstdio>

long long TL=1000000000;
class lint
{
private:
long long num[43];
int len;
public:
lint() {for(int i=0;i<43;i++) num[i]= i?0:2;len=0;}
lint& operator+=(const lint &a);
void print() {printf("%lld",num[len]);for(int i=len-1;i>=0;i--) printf("%018lld",num[i]);printf("\n");}
};
lint& lint::operator+=(const lint &a)
{
long long temp=0;
len=(len>a.len)?len:a.len;
for(int i=0;i<=len;i++)
{
num[i]+=a.num[i]+temp;
temp=num[i]/TL;
num[i]%=TL;
}
if(temp) len++,num[len]+=temp;
return *this;
}
lint ...<=1000;j++) d[j]+=d[j-1];
for(int i=2;i<=1000;i++)
{
for(int j=1000;j><=1000;j++) d[j]+=d[j-1];
}
while(scanf("%d",&n)!=EOF) d[n].print();
return 0;
}
问题参见joj 2419:http://acm.jlu.edu.cn/joj/showproblem.php?pid=2419
其实就是格子路径问题,但是有几点要注意
1、不能跑到对角线的上面^^
2、允许对角线路径
3、路径不能有往左或者往下的趋势,只能是按照向量(0,1) (1,0)(1,1)步进
4、注意到规模n达到了1000,这个导致从(0,0)到(n,n)的路径数达到近800位整数
。。。
以下是本人一个超时的程序,dp基于递推式
d[i][j]=d[i-1][j]+d[i][j-1]+d[i-1][j-1]
i==0 => d[i][j]=1
i<j => d[i][j]=0


#include <cstdio>

long long TL=1000000000;
class lint
{
private:
long long num[43];
int len;
public:
lint() {for(int i=0;i<43;i++) num[i]= i?0:2;len=0;}
lint& operator+=(const lint &a);
void print() {printf("%lld",num[len]);for(int i=len-1;i>=0;i--) printf("%018lld",num[i]);printf("\n");}
};
lint& lint::operator+=(const lint &a)
{
long long temp=0;
len=(len>a.len)?len:a.len;
for(int i=0;i<=len;i++)
{
num[i]+=a.num[i]+temp;
temp=num[i]/TL;
num[i]%=TL;
}
if(temp) len++,num[len]+=temp;
return *this;
}
lint d[1001];
int main()
{
TL*=TL;
int n;
for(int j=2;j<=1000;j++) d[j]+=d[j-1];
for(int i=2;i<=1000;i++)
{
for(int j=1000;j>=i;j--) d[j]+=d[j-1];
for(int j=i+1;j<=1000;j++) d[j]+=d[j-1];
}
while(scanf("%d",&n)!=EOF) d[n].print();
return 0;
}
0
显示全文

查看更多有趣的豆瓣小组

回应 (8条) 只看楼主

  • mister bin
    讨论OJ上的问题请到OJ的论坛!
  • Cysu
    catalan数……
  • Wendy
    I think u can use a graph instead of matrix to reduce the iterations
  • Earthson
    @Cysu 这不是catalan数。。。你再仔细看看 递推式多了一项
  • Earthson
    @Wendy 求graph的细节。。。
  • Earthson
    程序已经被我优化到限时内了。。。 0.83s/1s但是距离标程还是很有距离阿。。
  • Cysu
    @Earthson 哦对 没看到这句

    只能是按照向量(0,1) (1,0)“(1,1)“步进

    试试用母函数展开 应该可以得到一个组合数?
  • Earthson
    @Cysu 组合数学书上貌似有。。但是公式真的好复杂。。。。这个序列被称为大Schroder数。。。。如果直接按照公式算的话,时间复杂度貌似不减。。。
添加回应

算法与数据结构的热门贴

推荐小组

值得一读

    豆瓣
    我们的精神角落
    免费下载 iOS / Android 版客户端