?
题目大意：
第1天的时候，有一个空节点。之后每一天，每一个节点都会长一颗果实。并且再生成一个节点（每个节点最多生成K个节点）。
当果实的总数大于1234567890个时，就不会再生长了。问第N天的时候一共有多少个果实。
?
解题思路：
这个题目有显然的最优子结构问题，定义dp[i]等于某一个节点i天后生成的果实数。
那么dp[i] = i+dp[i-1]+dp[i-2]+...+dp[i-k];
具体的原因就是：某一个节点的总果实数等于他本身的i个加前一天生成的节点所增加的果实再加。。。。
?
而且能够看出来这个增长是平方级别的。那么复杂度大约就是根号1234567890。
?
?
#include#include typedef long long LL; #define maxn 66666 #define INF 1234567890 using namespace std; LL dp[maxn]; LL sum[maxn]; LL n,k; int main() { while(scanf(%lld %lld,&n,&k),n||k) { if(k ==0) { printf(%lld ,n-1>INF+1?INF+1:n-1); continue; } n--; memset(dp,0,sizeof dp); memset(sum,0,sizeof sum); LL ans = -1; for(int i = 1;i <= n;i++) { dp[i] = i + sum[i-1]; if(i-k-1>=0) dp[i]-= sum[i-k-1]; sum[i] = dp[i]+sum[i-1]; if(dp[i] > INF) { n = i; break; } } printf(%lld ,dp[n]); } return 0; }
?