SDUT 2765 - 母牛的故事
传送门
思路
上次校内选拔赛上的一道题目，晚上想起来就做了一下，一开始是用模拟的方法，TLE了。然后就想不到其他的方法，问了失踪同学才知道是Fibonacci数列。但是后来捣鼓了半天也没捣鼓出来，然后失踪提醒我用long long 试试，但是这时候我把一开始的递推式改了一下，又WA了。后来又改回原来的递推式才AC。以后算题目前一定要算一下数据范围TAT
就是Fibonacci数列。递推式
$cow[i] = cow[i - 1] + cow[i - m + 1], i > m$
代码
#include <cstdio>
using namespace std;
int main()
{
int year, m, i, j;
long long cow[1000];
while (~scanf("%d%d", &year, &m))
{
cow[1] = 1;
for (i = 2; i <= year; i++)
{
if (i - m <= 0)
cow[i] = cow[i - 1] + 1;
else
cow[i] = cow[i - 1] + cow[i - m + 1];
}
printf("%lld\n", cow[year]);
}
return 0;
}
- 上一篇杂记 III
- 下一篇UVa 10306 - e-Coins