Contents

1. 1. 描述:
2. 2. 输入：
3. 3. 输出:
4. 4. 样例输入:
5. 5. 样例输出:
6. 6. 题目大意：
7. 7. 分析：

描述:

There are N children standing in a line. Each child is assigned a rating value.
You are giving candies to these children subjected to the following requirements:
(1) Each child must have at least one candy.
(2) Children with a higher rating get more candies than their neighbors.
What is the minimum candies you must give?

输入：

The input consists of multiple test cases.
The first line of each test case has a number N, which indicates the number of students.
Then there are N students rating values, 1 <= N <= 300, 1 <= values <= 10000.

输出:

The minimum number of candies you must give.

样例输入:

[plain] view plain copy print?
5
1 2 3 4 5
5
1 3 5 3 6

样例输出:

[plain] view plain copy print?
15
9

题目大意：

求最少要发多少糖果，一群小孩站成一排，每个小孩手里有一个数，数大的小孩要比相邻
的数小的小孩拿的糖果数多些，每个人手里至少一个糖果

分析：

三种情况： 比左边大，比右边大，比左、右都大

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int arr[1010];
int b[1010];

int main(){

    int n;
    while(scanf("%d", &n) == 1){
        int sum = 0;
        memset(arr, 0, sizeof(arr));
        for(int i = 1; i <= n; i++)
            b[i] = 1;
        b[0] = 0;
        for(int i = 1; i <= n; i++)
            scanf("%d", &arr[i]);
        for(int i = 1; i <= n; i++){
            if(arr[i] > arr[i - 1]){
                b[i] = b[i - 1] + 1;
            }
        }
        for(int i = n; i >= 1; i--){
            if(arr[i] < arr[i - 1]){
                b[i - 1] = b[i] + 1;
            }
        }
        for(int i = 1; i <= n; i++){
            if(arr[i] > arr[i + 1] && arr[i] > arr[i - 1])
                b[i] = max(b[i + 1] + 1, b[i - 1] + 1);
        }
        for(int i = 1; i <= n; i++)
            sum += b[i];
        printf("%d\n", sum);
    }
    return 0;
}