Source
杭电ACM集训队训练赛（VIII）
望洋兴叹
11111111111111
#include <stdio.h> const int maxn=1000;
int m[1002][1000]={{0},{1,1},{1,1}}; int f[1002][1000]={{0},{1,0},{1,1}}; void add(int a[],int b[],int c[]) { int i;
for (i=0;i<=a[0];i++) c[i]=a[i]; if (b[0]>c[0]) c[0]=b[0];
for (i=1;i<=c[0];i++) { c[i]+=b[i]; if (c[i]>9) { c[i]-=10; c[i+1]++; } if (c[c[0]+1]>0) c[0]++; }
int main() {
int i,n; for (i=3;i<=maxn+1;i++) {
add(m[i-1],f[i-1],m[i]); add(f[i-1],m[i-2],f[i]); }
}
while (scanf("%d",&n)!=EOF) { for (i=m[n+1][0];i>0;i--) printf("%d",m[n+1][i]); printf("\\n"); }
return 0; }
思路如下：
一个长度n的队列可以看成一个n - 1的队列再追加的1个小孩，这个小孩只可能是：
a.男孩，任何n - 1的合法队列追加1个男孩必然是合法的，情况数为f[n - 1]；
b.女孩，在前n - 1的以女孩为末尾的队列后追加1位女孩也是合法的，我们可以转化为n - 2的队列中追加2位女孩；
一种情况是在n - 2的合法队列中追加2位女孩，情况数为f[n - 2]；
但我们注意到本题的难点，可能前n - 2位以女孩为末尾的不合法队列（即单纯以1位女孩结尾），也可以追加2位女孩成为合法队列，而这种n - 2不合法队列必然是由n - 4合法队列+1男孩+1女孩的结构，即情况数为f[n - 4]。
若感觉本题较难，可先查看文章：[ACM_HDU_2045]LELE的RPG难题，思路与本题类似，但较为简单。
得出递推公式如下：
f[n] = f[n - 1] + f[n - 2] + f[n - 4]还有需要注意的是本题中可能得出极大的数字，如当n为1000时，结果为：
12748494904808148294446671041721884239818005733501580815621713101333980596197474744336199742452912998225235910891798221541303838395943300189729514282623665199754795574309980870253213466656184865681666106508878970120168283707307150239748782319037
这种超大数完全不是C++提供的数值类型能够储存的，因此我们可以使用二维数组来模拟超大数运算，代码如下：
[cpp] view plaincopyprint? #include<stdio.h>
int main(){ int n;
int f[1001][101] = {0}; f[0][1] = 1; f[1][1] = 1; f[2][1] = 2; f[3][1] = 4;
for(int i = 4; i < 1001; ++i){ for(int j = 1; j < 101; ++j){
f[i][j] += f[i - 1][j] + f[i - 2][j] + f[i - 4][j]; //数组的每一位相加
f[i][j + 1] += f[i][j] / 10000; //超过4位的部分保存至数组下一位中 f[i][j] %= 10000; //每位数组只保存其中4位 } }
while(scanf("%d", &n) != EOF){ int k = 100;
while(!f[n][k--]); //排除前面为空的数组
printf("%d", f[n][k + 1]); //输出结果的前四位 for(; k > 0; --k){
printf("d", f[n][k]); //输出其余的所有四位数字，若数字小于四位，则前面用0填充 }
printf("\\n"); }
return 0; }
母牛的故事
Time Limit : 2000/1000ms (Java/Other) Memory Limit : 65536/32768K (Java/Other)
Total Submission(s) : 36 Accepted Submission(s) : 21 Problem Description
有一头母牛，它每年年初生一头小母牛。每头小母牛从第四个年头
开始，每年年初也生一头小母牛。请编程实现在第n年的时候，共有多少头母牛？
Input
输入数据由多个测试实例组成，每个测试实例占一行，包括一个整数n(0<n<55)，n的含义如题目中描述。
n=0表示输入数据的结束，不做处理。
Output
对于每个测试实例，输出在第n年的时候母牛的数量。 每个输出占一行。
Sample Input 2450
Sample Output 246
Author lcy
我的错误代码
#include<stdio.h> int main() {
int n,i;
int a[55]={2,2,3,4}; for(i=4;i<55;i++) {
a[i]=a[i-3]*3; }
while(scanf("%d",&n)!=EOF&&n!=0) {
printf("%d\\n",a[n-1]); }
return 0; }
111111111111111 #include<stdio.h> int main() {
int n,s[100],i,sum;
while(scanf("%d",&n)!=EOF) {
if(n==0)break; s[0]=s[1]=s[2]=0;
s[3]=1;
for(i=1;i<n;i++) {
s[3]=s[3]+s[2];//a[i]=a[i-1]+a[i-2] s[2]=s[1]; s[1]=s[0]; s[0]=s[3]; }
sum=s[0]+s[1]+s[2]+s[3];
printf("%d\\n",sum); }
return 0; }
递推题，它们写出来的代码都很简单。但关键看你能不能找到规律。 本题中，第n年的牛的来源有2中:
第n-1年的牛
第n-3年的牛所生的小牛
而递推的出口是第1年为1头，第2年为2头，第3年为3头。
#include<iostream> using namespace std;
int main() {
int fab[55]={1,2,3,4,6}; int i,n;
for (i = 5 ; i < 55 ; i++) fab[i] = fab[i - 1] + fab[i - 3];
while (cin>>n&&n) {
printf("%d\\n", fab[n - 1]); }
return 0; }