zoj 3149 Breadtree(樸素DP)

zoj 3149 Breadtree(樸素DP)

題目大意：

第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;
}