一.减肥1

方法一：简单的动态规划题目。状态转移方程：
       f[i][0]：从0到第i分钟，其中第i分钟休息能得到的最优值
       f[i][1]：从0到第i分钟，其中第i分钟做一个俯卧撑能得到的最优值  
       f[i][2]：从0到第i分钟，其中第i分钟做两个俯卧撑能得到的最优值       
　　   f[i][0]=max(f[i-1][0],f[i-1][1],f[i-1][2]);
　　   f[i][1]=max(f[i-1][0],f[i-1][1])+v[i];
　　   f[i][2]=max(f[i-1][0],f[i-1][1])+v[i]*v[i]; 
       目标：max(f[t,0],f[t,1],f[t,2])   边界：f数组清零   预计得分100

       时间复杂度：O(N)
       空间复杂度：O(N)
方法二：由于我们发现本次状态只跟上次有关，可以使用一个f[2][3]的滚动数组优化空间。    预计得分100
       时间复杂度：O(N)
       空间复杂度：O(1)

方法一：纯模拟，每次询问都扫描询问的区间求出最大值，并且进行更改。预期分数40分

        时间复杂度：O(N+kM)
        k为平均询问区间长度

方法二：使用线段树。首先建一棵线段树，除了线段树必要的num,l,r之外，记录下来区间最大值Max和当前区间最大值所在位置pos，询问时返回Max和pos，并写一更改函数对pos上的值进行更改并递归返回上层也进行更改。 预期分数100分
       时间复杂度：O((N+M)logN)
       空间复杂度：O(N)

  树形动规：
  根据题意，这些间谍关系构成一棵树（无环）
  依次讨论以每个点作为消息的起点，传遍整棵树所需最小时间，记录其中最小者。
  即依次以每个点作为整棵树的根节点进行讨论。
  f[i][j]表示消息传遍以i为根的子树(并且i的父亲为j）所需最小时间。 f[i][0]表示i为整棵树的根节点。
        若s1,s2,..,sk为i的孩子，消息传遍以它们为根的子树的最小时间分别为f[s1][i],f[s2][i],..,f[sk][i]
        若有x棵子树的f值都为y，那么消息传遍这x棵子树所需最小时间为 y+x-1,同时将这x棵子树看成一棵传递时间需y+x-1的子树。
  那么f[i][j]=max{f[s][i]}+t-1   t表示值为f[s][i]的子树的个数