題目描述：
　　給從左至右排好隊(duì)的小朋友們分糖果，
　　要求：
　　1.每個(gè)小朋友都有一個(gè)得分，任意兩個(gè)相鄰的小朋友，得分較高的所得的糖果必須大于得分較低的，相等則不作要求。
　　2.每個(gè)小朋友至少獲得一個(gè)糖果。
　　求，至少需要的糖果數(shù)。
　　輸入：
　　輸入包含多組測試數(shù)據(jù)，每組測試數(shù)據(jù)由一個(gè)整數(shù)n（1<=n<=100000）開頭，接下去一行包含n個(gè)整數(shù)，代表每個(gè)小朋友的分?jǐn)?shù)Si（1<=Si<=10000）。
　　輸出：
　　對(duì)于每組測試數(shù)據(jù)，輸出一個(gè)整數(shù)，代表至少需要的糖果數(shù)。
　　樣例輸入：
　　3
　　1 10 1
　　3
　　6 2 3
　　2
　　1 1樣例輸出：
　　4
　　5
　　2這題可以把所有的人看成圖中的一個(gè)點(diǎn)，兩個(gè)相鄰的人如果s的值不一樣的話可以從大的往小的連一條邊，可以很明顯的看出，這些人與這些邊構(gòu)成了有向無環(huán)圖。那么所有人的最小能分配到的糖果值就可以通過他的左右兩個(gè)人計(jì)算出來。可以采用記憶化搜索算法。復(fù)雜度是O（n） www.lefeng123.com
　　AC代碼： #include
　　#include
　　#include
　　#define MAX 100001
　　using namespace std;
　　int cal（int r,int n,int dp[],int A[]）
　　{
　　if（dp[r]>0）
　　return dp[r];//已經(jīng)計(jì)算過
　　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;
　　}