第2回北京林業大学「計ニンニク客」杯プログラム設計コンテストC題Candy

タイトルリンク
Candy
時間制限(C/C+):1000 MS/3000 MS運転メモリ制限:65536 KByte
総提出:21試験合格:11
説明
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.
サンプル入力

5
1 2 3 4 5
5 
1 3 5 3 6

サンプル出力

15
9

テーマソース
BJFUACM
[提出][提出状況][討論版]
前後からインクリメントを探す

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int a[305];
int dp1[305],dp2[305];
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        for(int i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
        }
        memset(dp1,0,sizeof(dp1));
        memset(dp2,0,sizeof(dp2));
        dp1[0]=1;
        for(int i=1;i<n;i++)
        {
            if(a[i]>a[i-1])
            {
                dp1[i]=dp1[i-1]+1;
            }
            else
            {
                dp1[i]=1;
            }
        }
        dp2[n-1]=1;
        for(int i=n-2;i>=0;i--)
        {
            if(a[i]>a[i+1])
            {
                dp2[i]=dp2[i+1]+1;
            }
            else
            {
                dp2[i]=1;
            }
        }
        int ans=0;
        for(int i=0;i<n;i++)
        {
           // printf("%d %d
",dp1[i],dp2[i]);
            ans+=max(dp1[i],dp2[i]);
        }
        printf("%d
",ans);
    }

}