动态规划-糖果分配

candy糖果分配
有N个孩子站成一行,每个孩子有不同的评估值。
分配糖果给这些孩子,受到如下条件的限制:

  1. 每个孩子必须至少有一颗糖果
  2. 有更高评估值的孩子比他的邻居有更多的糖果
    问:必须分配的最少糖果是多少。

找最大最小值,这种问题叫做寻优问题,也叫做规划问题。

分析:

  1. dp[i]:表示0-i的最少糖果,val[i]:表示i的评估值,c[i]:表示i的糖果
  2. $$dp[i+1]=
    \begin{cases}
    dp[i]+1, & \text{val[i+1] <= val} \\[2ex]
    dp[i]+val[i]+1, & \text{val[i+1] >val}
    \end{cases}$$
  3. 2步骤可能出现dp[i]==dp[i+1]==1,需要从右往左进行运算
    使得,c[i-1] = c[i-1]+1,if val[i-1] > val[i]

操作过程:

  1. 从左向右扫描后能保证比左边邻居大1
  2. 从右向左扫描后能保证比右边邻居大1
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    int candy(vector<int> &ratings) {
    int n = ratings.size();
    vector<int> v(n,1);
    for( int i = 1;i < n;i++)
    if(ratings[i]>ratings[i-1]) v[i] = v[i-1]+1;
    int sum = 0;
    for( int i = n-1;i > 0;i--){
    if(ratings[i-1]>ratings[i]&&v[i-1]<=v[i]) v[i-1] = v[i] + 1;
    sum += v[i];
    }
    sum += v[0];
    return sum;
    }
-------------本文结束感谢您的阅读-------------
鼓励鼓励!