zoj 3149 Breadtree - c++编程基础

D - Breadtree Crawling in process... Crawling failed Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%lld & %llu Submit Status

Description

Breadtree is a kind of tree that produces bread. At its first year, a breadtree is only a node with a bread of weight 0 on this node which is also called zeronode. Every year after that, the weight of bread on each node of the tree will increase by 1, and another branch with a zeronode will grow at the end of each node. However, there is a limit of branches on each node. That is, when the number of branches of a node reaches the limit, there won't be any more branches, but the weight of its bread will still increase. What's more, a breadtree remains unchanged when the total weight of bread is larger than 1234567890.

Input

There are two integers N and K on each line. N is a positive integer fit in signed 32-bit integer. K is a non-negative integer fit in signed 32-bit integer. An N equals to 0 signals the end of input, which should not be processed.

Output

Output the total weight of bread on a breadtree with branches limit K in the N-th year in a line for each case.

Sample Input

Sample Output

题意: 树上有节点，节点上有面包，节点每天分出一个分支（到达k后不再分），节点上面的面包每天增重1（到达1234567890后不增），给出n天和k，问第n天面包总重。（n、k都为32为整数）

思路：开始想的是用一个dp[i]表示面包重为 i 的节点个数，一个sum[i]表示其前缀和，然后模拟树的伸张过程，复杂度有点高TLE了。正确的思路为：dp[i]表示第i年的总重量（可将一开始看做第0年），则dp[0]=0, 在第i年根重 i ，其余子树重量为第(i-1)年..第(i-k)年的重量和，用一个sum[i]维护，然后直接循环就好了，注意k=0的特判就好了。
代码：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
         #include 
         
           #include 
          
            #include 
           
             #include 
            
              #pragma comment (linker,"/STACK:102400000,102400000") #define maxn 100005 #define MAXN 16005 #define mod 1000000000 #define INF 0x3f3f3f3f #define pi acos(-1.0) #define eps 1e-6 typedef long long ll; using namespace std; ll n,m,k,ans,cnt,tot,flag; ll dp[maxn],sum[maxn]; ll xx=1234567890; ll solve() { ll i,j,d,t; dp[0]=sum[0]=0; for(i=1;i<=n;i++) { dp[i]=i+sum[i-1]-sum[max(0LL,i-k-1)]; sum[i]=sum[i-1]+dp[i]; if(dp[i]>xx) return dp[i]; } return dp[n]; } int main() { ll i,j,t; while(scanf("%lld%lld",&n,&k),n|k) { n--; if(k==0) { printf("%lld\n",min(n,xx+1)); continue ; } ans=solve(); printf("%lld\n",ans); } return 0; } /* 10000 0 101 1 10 2 1221 128 0 0 */