HDOJ1087 Super Jumping! Jumping! Jumping!

Super Jumping! Jumping! Jumping!

http://acm.hdu.edu.cn/showproblem.php?pid=1087

分析：

簡單的動态規劃題。題目的意思很直白，其實就是尋找最長遞增子序列。

假設dp[i]表示的是從start到達第i個點時可獲得的最大分數，data[i]表示的是第i個點的分數值，那麼可以得到，

dp[i]= max{dp[i]，dp[j]+data[i] }，

其中，j<i，且data[j]<=data[i]，即j表示的是每一個在i前面且其分數值不大于data[i]的點，計算完dp之後，結果很明顯就是dp中的最大值。

AC代碼如下：

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
	int n;
	int dp[1005],data[1005]; 
	while(cin>>n&&n)
	{
		for(int i=1;i<=n;i++)
		{
			cin>>data[i];
			dp[i]=data[i];
		}
		dp[0]=data[0]=0;
		int ans=0;
		for(int i=1;i<=n;i++)
		{
			for(int j=i+1;j<=n;j++)
			{
				if(data[j]>data[i])
				{
					dp[j]=max(dp[j],dp[i]+data[j]);
				}
			}
			ans=max(dp[i],ans);
		}
		cout<<ans<<endl;
	}
	return 0;
}