学步园

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

解题思路：求最长上升子序列和的最大值

#include <stdio.h><br /> #define GetMax(a,b) a>b?a:b<br /> #define Big __int64<br /> Big dp[1005]={0};<br /> int main()<br /> {<br /> Big Max;<br /> int i,j,n,val[1005]={0};<br /> while (scanf("%d",&n),n)<br /> {<br /> for(i=1;i<=n;i++)<br /> scanf("%d",&val[i]),dp[i] = 0;<br /> dp[1] = val[1];<br /> for (i=1;i<=n;i++)<br /> {<br /> for (j=i+1;j<=n;j++)<br /> {<br /> if (val[j]>val[i])<br /> dp[j] = GetMax(dp[j],dp[i]+val[j]);<br /> else if(dp[j]==0)/*之前没有比它小的数，则最大和为自己本身*/<br /> dp[j] = val[j];<br /> }<br /> }<br /> Max = -1;<br /> for (i=n;i>=0;i--)<br /> if(Max<dp[i])<br /> Max = dp[i];<br /> printf("%I64d/n",Max);<br /> }<br /> return 0;<br /> }