第2题：母牛生小牛
这一题呢，我用了许多种尝试，刚开始用了递归暴力模拟，我想大家都能看懂。
#include <bits/stdc++.h>
using namespace std;
unsigned long long n;
unsigned long long ss(unsigned long long x){unsigned long long y=x+3;unsigned long long ans=1;if(y<=n)ans+=ss(y);for(unsigned long long i=y+2;i<=n;i+=2)ans+=ss(i);return ans;
}
int main(){cin>>n;cout<<ss(0);return 0;
}
40分
后面几个点都TLE了
只有unsigned long long呢，它可以将long long负数存储的那些空间全部挪到存正数的空间里来。
我加了个记忆化，然后提交
#include <bits/stdc++.h>
using namespace std;
unsigned long long n,sum[1010];
unsigned long long ss(unsigned long long x){if(sum[x]!=0)return sum[x];unsigned long long y=x+3;unsigned long long ans=1;if(y<=n)ans+=ss(y);for(unsigned long long i=y+2;i<=n;i+=2)ans+=ss(i);sum[x]=ans;return ans;
}
int main(){cin>>n;cout<<ss(0);return 0;
}
60分
后面几个点都WA了
这很明显，能推出状态转移方程，于是，我推了，还加了个高精。
我的状态表示是f[i]表示在第i年出生的小牛，到第n年，总共会创造有多少头奶牛，包括他本生。
#include <bits/stdc++.h>
using namespace std;
string dp[1010];
int x[510],y[510];
string jf(string a,string b){memset(x,0,sizeof(x));memset(y,0,sizeof(y));if(a.size()<b.size())swap(a,b);int c=-1,l1,l2,d=-1;for(int i=a.size()-1;i>=0;i--){c++;x[c]=a[i]-48; }l1=a.size();for(int i=b.size()-1;i>=0;i--){d++;y[d]=b[i]-48; }l2=b.size();for(int i=0;i<l1;i++){y[i]+=x[i];y[i+1]+=y[i]/10;y[i]%=10;}string s="";if(y[l1]!=0)s+=to_string(y[l1]);for(int i=l1-1;i>=0;i--)s+=to_string(y[i]);return s;
}
int main(){int n;cin>>n;for(int i=n;i>=0;i--){int y=i+3;dp[i]='1';for(int j=y;j<=n;j+=2)dp[i]=jf(dp[i],dp[j]);}cout<<dp[0];return 0;
}
代码出来了，80分，最后2个点TLE了
很显然，状态状态转移方程太复杂。
我们来列个表看看。
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|
| 1 | 1 | 2 | 2 | 3 | 4 | 5 | 7 | 9 |
咦，好像有什么规律呢！
从第4项开始，每项都是前2项和前3项的和，哇！
#include <bits/stdc++.h>
using namespace std;
string dp[1010];
int x[510],y[510];
string jf(string a,string b){memset(x,0,sizeof(x));memset(y,0,sizeof(y));if(a.size()<b.size())swap(a,b);int c=-1,l1,l2,d=-1;for(int i=a.size()-1;i>=0;i--){c++;x[c]=a[i]-48; }l1=a.size();for(int i=b.size()-1;i>=0;i--){d++;y[d]=b[i]-48; }l2=b.size();for(int i=0;i<l1;i++){y[i]+=x[i];y[i+1]+=y[i]/10;y[i]%=10;}string s="";if(y[l1]!=0)s+=to_string(y[l1]);for(int i=l1-1;i>=0;i--)s+=to_string(y[i]);return s;
}
int main(){int n;cin>>n;dp[1]='1';dp[2]='1';dp[3]='2';for(int i=4;i<=n;i++)dp[i]=jf(dp[i-2],dp[i-3]);cout<<dp[n];return 0;
}
这就是AC代码
