北京林業大学校試合-C題(Candy)

タイトルリンククリックでリンクを開く
これは貪欲な問題に似ていて、もし1人の子供が周囲の子供よりratingが高いならば、彼が得たキャンディの数は周囲のより高いはずですが、最後に私たちに最小の総キャンディの数を求めましょう!!
では、左から右への順番を考えて、隣を探して、まず1番目をキャンディ数1にします.後のスキャンでは、現在の子供が左の子供よりratingが高い場合、現在の子供のキャンディ数は左の子供のキャンディ数に1を加えて、1だけ加えて、左から右への順番を満たすのが最小です.この时、私达は右から左の顺番を満たす必要があります.私达は最后の1を右から左にスキャンして、もし今の子供ratingが彼の右の隣のratingより高いならば、更に今の子供のキャンディの数と右の子供のキャンディの数+1を比较して、谁が谁を取って、あなた达の2つの辺はすべて条件を満たさなければならないので、合理的で、だから谁が谁を取っています!!

#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
#include <stack>
#include <queue>                      
#include <map>
#include <vector>
#include <cmath>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1                                  
using namespace std;
const int maxn = 55555;
struct node
{
	int ca, va;
	node(){}
	node(int va,int ca):va(va),ca(ca){}
}node1[333];

int main(void)
{
	//freopen("in.txt", "r", stdin);
	int n;

	while (scanf("%d", &n) != EOF)
	{
		int i;
		for (i = 0; i < n; i++)
		{
			int va;
			scanf("%d", &va);
			node1[i] = node(va, 1);							//       1
		}
		for (i = 1; i < n; i++)
		{
			if (node1[i].va > node1[i - 1].va)
				node1[i].ca = node1[i - 1].ca + 1;
		}
		int total = node1[n-1].ca;
		for (i = n - 2; i >= 0; i--)
		{
			if (node1[i].va > node1[i + 1].va&&node1[i].ca < node1[i + 1].ca + 1)    //    ，                    
				node1[i].ca = node1[i + 1].ca + 1;
			total += node1[i].ca;
		}
		printf("%d
", total);
	}
	return 0;
}