AcWing 461. 金币(递归的解法)
原题链接
简单
作者:
orange0912
,
2020-07-26 00:48:13
,
所有人可见
,
阅读 699
#include <iostream>
#include <cstdio>
using namespace std;
int x[10001]={0};//x[i]第i天的金币数
int k;
void f( int i, int j ,int t ) //f(i,j,t) 第i天会获得j个金币 而且已经连续t天拿到了j个金币
{
if(i>k) return;//若天数已经超过了k天,则无需继续,递归出口
x[i]=j;
//接下来要处理第i+1天的情况了
if(t==j) //已经连续t天(j天)拿到了金币数j个
f(i+1 , j+1 , 1);//下一天获取j+1个金币,累计连续1天
else if(t<j)
f(i+1, j, t+1 );//下一天获取j个金币,累计连续t+1天
}
//获取x数组的前k项和
int g(int k)
{
if(k==1) return 1;
return g(k-1)+ x[k] ;//前k-1天的和加上第k天的金币
}
int main( )
{
int i,j,s=1,r=0,d=2;
cin>>k;
f(1,1,1);
cout<< g(k);
return 0;
}
//金币数 1 2 2 3 3 3 4 4 4 4
//第i天 1 2 3 4 5 6 7 8 9 10
// * * * *