HDU 1087

题意：求上升序列的最大和。

思路：简单DP。两重循环：dp[i]表示以v[i]结尾的最大和。状态转移方程dp[i]=max(dp[j]+v[i],dp[i]) (在v[j]<v[i]的前提下。表示能够从j跳到i)

AC代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int main()
{
	int n,dp[1005],v[1005];
	while(scanf("%d",&n)!=EOF)
	{
	  if(n==0) break;
	  for(int i=1;i<=n;i++)
	  scanf("%d",&v[i]);
	  for(int i=1;i<=n;i++)
	  {
	    dp[i]=v[i];
	    for(int j=1;j<i;j++)
		{
		  if(v[j]<v[i])
		  {
		    if(dp[j]+v[i]>dp[i])
			dp[i]=dp[j]+v[i];
		  }
		}
	  }
	  int maxx=0;
	  for(int i=1;i<=n;i++)
	  {
	    if(dp[i]>maxx)
		maxx=dp[i];
	  }
	  printf("%d
",maxx);
	}
	return 0;
}