第2题：母牛生小牛
kradcigam
2019-07-21 14:22:52
# 第2题：母牛生小牛
这一题呢，我用了许多种尝试，刚开始用了递归暴力模拟，我想大家都能看懂。
```cpp
#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负数存储的那些空间全部挪到存正数的空间里来。
我加了个记忆化，然后提交
```cpp
#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年，总共会创造有多少头奶牛，包括他本生。
```cpp
#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项的和，哇！
```cpp
#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代码