記憶化搜索算法之動態規劃

題目描述：

給從左至右排好隊的小朋友們分糖果，
要求：
1.每個小朋友都有一個得分，任意兩個相鄰的小朋友，得分較高的所得的糖果必須大於得分較低的，相等則不作要求。
2.每個小朋友至少獲得一個糖果。
求，至少需要的糖果數。

輸入：

輸入包含多組測試數據，每組測試數據由一個整數n（1<=n<=100000）開頭，接下去一行包含n個整數，代表每個小朋友的分數Si（1<=Si<=10000）。

輸出：

對於每組測試數據，輸出一個整數，代表至少需要的糖果數。

樣例輸入：

3
1 10 1
3
6 2 3
2
1 1

樣例輸出：

4
5
2

這題可以把所有的人看成圖中的一個點，兩個相鄰的人如果s的值不一樣的話可以從大的往小的連一條邊，可以很明顯的看出，這些人與這些邊構成了有向無環圖。那麼所有人的最小能分配到的糖果值就可以通過他的左右兩個人計算出來。可以采用記憶化搜索算法。復雜度是O(n)

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];//已經計算過
	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;
}