这题可以把所有的人看成图中的一个点，两个相邻的人如果s的值不一样的话可以从大的往小的连一条边，可以很明显的看出，这些人与这些边构成了有向无环图。那么所有人的最小能分配到的糖果值就可以通过他的左右两个人计算出来。可以采用记忆化搜索算法。复杂度是O(n)

#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAX 100001

using namespace std;

int cal(int r,int n,int dp[],int A[])
{
	if(dp[r]>0)
		return dp[r];//已经计算过
	dp[r]=1;
	if(r+1<=n&&A[r]>A[r+1])//右边有人比他小，要受右边限制
		dp[r]=max(dp[r],cal(r+1,n,dp,A)+1);
	if(r-1>=1&&A[r]>A[r-1])//左边有人比他小，要受左边限制
		dp[r]=max(dp[r],cal(r-1,n,dp,A)+1);
	return dp[r];
}

int main(int argc,char *argv[])
{
	int n;
	int A[MAX];
	int dp[MAX];
	while(scanf("%d",&n)!=EOF)
	{
		int i;
		memset(dp,0,sizeof(dp));
		for(i=1;i<=n;i++)
			scanf("%d",&A[i]);
		long long sum=0;
		for(i=1;i<=n;i++)
			sum+=cal(i,n,dp,A);
		printf("%lld\n",sum);
	}

	return 0;
}