母牛的故事

0
11

一道DP的题,规律的话多写几组就找到了

因为想到小母牛的存在就定义了dp[i][2];

第n年的母牛等于去年的加上前第三年新生的小母牛

第n年的小母牛等于去年的母牛加上去年小母牛(减去今年长大的母牛加上今年刚长大的母牛生下的小牛)

下面是代码:

#include <iostream>
#include <string>
#include <cstdio>
using namespace std;

int main(){
int dp[55][2],n;
for(int i=1;i<5;i++){//初始化
dp[i][0]=1;
dp[i][1]=i-1;
}
for(int i=5;i<55;i++){
dp[i][0]=dp[i-3][0]+dp[i-3][1];//dp[i-1][0]+dp[i-3][0];
dp[i][1]=dp[i-1][0]+dp[i-1][1];
}
while(1){
scanf(“%d”,&n);
if(n==0)break;
printf(“%d\n”,dp[n][0]+dp[n][1]);
}
return 0;
}

<

发布回复

请输入评论!
请输入你的名字