HDU 1087 && POJ 2533(DP,最长上升子序列).

~~~~

两道题的意思差不多，HDU上是求最长上升子序列的和，而POJ上就的是其长度。

貌似还有用二分写的nlogn的算法，不过这俩题n^2就可以过嘛。。

~~~~

题目链接:

?

~~~~

HDU1087:

?

#include
  
   
#include
   
     #include
    
      #define INF 0x7fffffff #define N 1111 using namespace std; int f[N],a[N]; int main() { int n; while(~scanf(%d,&n),n) { for(int i=1;i<=n;i++) { scanf(%d,&a[i]); f[i]=a[i]; } int ans=f[1]; for(int i=2;i<=n;i++) { for(int j=1;j
     
      a[j]) f[i]=max(a[i]+f[j],f[i]); } ans=max(ans,f[i]); } printf(%d ,ans); } return 0; } 
     
    
   
  

?

POJ 2533:

?

#include
  
   
#include
   
     #include
    
      #define INF 0x7fffffff #define N 1111 using namespace std; int f[N],a[N]; int main() { int n; while(~scanf(%d,&n)) { for(int i=1;i<=n;i++) { scanf(%d,&a[i]); f[i]=1; //~~ } int ans=f[1]; for(int i=2;i<=n;i++) { for(int j=1;j
     
      a[j]) f[i]=max(1+f[j],f[i]); //~~ } ans=max(ans,f[i]); } printf(%d ,ans); } return 0; } 
     
    
   
  

?