本文共 1139 字，大约阅读时间需要 3 分钟。
递推公式：f[n]=f[n-1]+f[n-2]+f[n-4]; 突破口：如何得到递推公式，主要是最后一个f[n-4]，这个稍作解释，假如第n,n-1个都是女孩，也就是n-2个人都站好了以后，末尾再插上两个女孩，这个时候，本来以MF结尾的站法是不合法的，但是由于插上了两个FF，成了MFFF，使得这种站法成了合法的，因此这时就相当于将MFFF插到n-4个人排好之后的合法队列后方，因此加上f[n-4]。
代码如下：
#include#include using namespace std;long long a[1001][30]; //数据很大要用大数，数组每个元素存储1~1e16位的数字int main(){ int n,i,j,start,first; long long mod=1; for(i=1;i<=17;i++) //mod=1e17； { mod*=10; } memset(a,0,sizeof(a)); a[1][29]=1;a[2][29]=2;a[3][29]=4;a[4][29]=7; for(i=5;i<=1000;i++) //递推公式:f[n]=f[n-1]+f[n-2]+f[n-4] { for(j=29;j>=0;j--) { a[i][j]=a[i-1][j]+a[i-2][j]+a[i-4][j]; } for(j=29;j>=0;j--) //相加完之后再进位，否则会出错 { if(a[i][j]>=mod) { a[i][j-1]=a[i][j-1]+a[i][j]/mod; a[i][j]%=mod; } } }/* for(i=0;i<=100;i++) { for(j=0;j<=19;j++) printf("%lld",a[i][j]); printf("\n");}*/ while(~scanf("%d",&n)) { start=0;first=1; for(i=0;i<=29;i++) { if(a[n][i]!=0) start=1; if(start) { if(first) //是第一个数字，就不用补0 { printf("%lld",a[n][i]); first=0; } else printf("%017lld",a[n][i]); //不是第一个数字，就要在前面补0，每个数字占17格（规律：等于mod的幂次） } } printf("\n"); } return 0;}
转载地址：http://hfdci.baihongyu.com/