学步园

注意：对最长上升子序列，理解不深刻，一直wa.....

题目分析：每次从左向右，找arr[i]>a[j]&&dp[i]最大的，

#include<iostream>
#include<cstdio>
using namespace std;
int arr[1010];
int dp[1010];
int main()
{
	int n;
	while(scanf("%d",&n)!=EOF)
	{
            if(n==0)
	       break;
	   for(int i=1;i<=n;i++)
		   scanf("%d",&arr[i]);
	    for(int i=1; i<=n; ++i)  
		dp[i] = 0;  
	   dp[1]=arr[1];
       int ans,temp=0,j;   
       for(int i=2; i<=n; ++i)  
       {  
           ans = 0;  
           for(j=1; j<i;j++)  
           {  
	       if(arr[i]>arr[j] && dp[j]>ans) 
	      {
	         ans = dp[j];
	      }
           } 
	  dp[i]=ans+arr[i];
       }  
       ans = 0;  
       for(int i=1; i<=n; ++i)  
       {  
	    if(dp[i]>ans)  
	     ans = dp[i];  
       }
	   printf("%d\n",ans);
     }
   system("pause");
   return 0;
}


/***************************样例能过，错的！！！
#include<iostream>
#include<cstdio>
using namespace std;
int arr[1010];
struct node
{
	__int64  no,w;
}dp[1010];
int main()
{
	int n;
	while(scanf("%d",&n)!=EOF)
	{
       if(n==0)
		   break;
	   for(int i=1;i<=n;i++)
		   scanf("%d",&arr[i]);
	   /*for(int i=1;i<=n;i++)
		   dp[i].w=0;
	    for(int i=1; i<=n; ++i)  
			dp[i].no = 0;  
	   dp[1].w=arr[1];
	   dp[1].no=1;
       __int64 ans,temp=0,j;   
       for(int i=2; i<=n; ++i)  
       {  
		   ans = dp[i].no;  
           for(j=1; j<i; ++j)  
           {  
			   if(arr[i]>arr[j] && dp[j].no>ans) 
			 {
				   ans = dp[j].no; 
				   //temp=j;
			 }
           }  
		   dp[i].no = ans+1;  
		   dp[i].w=dp[temp].w+arr[i];
       }  
       ans = 0;  
       for(int i=1; i<=n; ++i)  
       {  
		   if(dp[i].w>ans)  
			   ans = dp[i].w;  
        } 
	   /* for(int i=1; i<=n; ++i)  
       {  
		   if(dp[i].no>ans)  
			   ans = dp[i].no;  
        } 
		ans=dp[ans].w;
	   /*for(int i=1;i<=n;i++)
		   printf("%d  ",dp[i].w);
	   printf("\n\n");
	   printf("%I64d\n",ans);
	}
	system("pause");
	return 0;
}
*/

/*
#include<iostream>
#include<cstdio>
using namespace std;
int arr[1010],dp[1010];
//int B_search(int )
int main()
{
	int n;
	while(scanf("%d",&n)!=EOF)
	{
       if(n==0)
		   break;
	   for(int i=1;i<=n;i++)
		   scanf("%d",&arr[i]);
	   dp[1]=arr[1];
	   int c=1;
	   for(int i=2;i<=n;i++)
	   {
		   if(arr[i]>dp[j])
			       dp[++c]=arr[i];
		   else
		   {
		      for(int j=1;j<=c;j++)
		      {
			     if(arr[i]<=dp[j])
				      dp[j]=arr[i];
		      }
		   }
		   /*if(arr[i]<=dp[1])
			   dp[1]=arr[i];
		   else if(arr[i]>=dp[c])
		   {
               dp[++c]=arr[i];
		   }*/
		   /*else
		   {

             int low=1,high=i,mid;
			  while(low<=high)
			 {
                 mid=(low+high)/2;
			     if(dp[i]<arr[mid])
				     high=mid-1;
			     else
				     low=mid+1;
			 }  
	   }
	}
}
*/