Array

3
1
3
5

1
4
7

题目大意：一开始有一个数列{1}。每过一天，将当天的数列复制一遍，放在数列尾，并在两个数列间用0隔开，并且将当天新产生的所有数字（包括0）全加1。经过100天后，这个数列的前M项和是多少？

通过观察数列可以发现递推公式：f(n)=2*f(n-1)+2^(n-1)，n表示天数，f(n)表示第n天数列的和

本来想求出通项公式，直接算第n天的数列和，然后再通过函数递推得到最终结果，但高中数学能力已远离我，这么简单的求通项公式都能算错好几次，导致最终没时间理清递推关系式。

前n项的和由2部分组成：前day天形成的数列的和 + 剩余的 n-((1LL<<day)-1)项的和

对于剩余的n-((1LL<<day)-1)项，每项减去1，共提出n-((1LL<<day)-1)，剩下的第一项为0，其余的n-((1LL<<day)-1)-1项又可以形成新的前某项，由此形成递推

【语文功底太渣，只能这样表述了】

#include <cstdio>
using namespace std;
long long dfs(long long n) {//dfs(n)返回前n项的和
if(n<=0)
return 0;
long long cur=0,day=0;//cur表示第day天产生的数列的和；day表示天数
while(n>=(1LL<<day)) {//如果剩余的项数大于等于第day+1天比第day天多出的项数，则进入循环，否则跳出循环
cur=(cur<<1)+(1LL<<day);//递推公式：f(n)=2*f(n-1)+2^(n-1)，n表示天数，f(n)表示第n天数列的和
n-=1LL<<day;//剩余项数减去用掉的项数
++day;//天数+1
}
return cur+dfs(n-1)+n;//
}
int main() {
int T;
long long n;
scanf("%d",&T);
while(T--) {
scanf("%I64d",&n);
printf("%I64dn",dfs(n));
}
return 0;
}

通项公式：f(n)=(n+1)*2^(n-1)

安静下来终于理清关系了，可以替换上面的dfs函数

long long dfs(long long n) {//dfs(n)返回前n项的和
if(n<=0)
return 0;
long long day=0;//day表示天数
while(n>=(2LL<<day)-1)
++day;
n-=(1LL<<day)-1;
return day*(1LL<<(day-1))+dfs(n-1)+n;
}

暂不会，待解决……

暂不会，待解决

最后

以上就是爱撒娇小甜瓜为你收集整理的HDU-5587 Array（DFS） Array的全部内容，希望文章能够帮你解决HDU-5587 Array（DFS） Array所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。