最长上升子序列LIS集合 POJ2533，POJ1631,POJ1887,POJ1609 - JAVA

.x && node[i].y >= node[j].y) dp[i] = dp[j] + 1; if(dp[i] > ans) ans = dp[i]; } } printf("%d\n",ans); } return EXIT_SUCCESS; }

还有另一种做法，因为范围还是比较小的，所以可以直接dp做

#include
                                           
                                            
#include
                                            
                                              #include
                                             
                                               #include
                                              
                                                #include
                                               
                                                 #include
                                                
                                                  #include
                                                 
                                                   #include
                                                  
                                                    #include
                                                    #include
                                                    
                                                      #include
                                                     
                                                       #include
                                                      
                                                        #include
                                                       
                                                         #define ll long long #define eps 1e-7 #define inf 0xfffffff //const ll INF = 1ll<<61; using namespace std; //vector
                                                        
                                                          > G; //typedef pair
                                                         
                                                           P; //vector
                                                          
                                                            > ::iterator iter; // //map
                                                           
                                                            mp; //map
                                                            
                                                             ::iterator p; //#define IN freopen("c:\\Users\\linzuojun\\desktop\\input.txt", "r", stdin) //#define OUT freopen("c:\\Users\\linzuojun\\desktop\\output.txt", "w", stdout) int num[112][112],dp[112][112]; void clear() { memset(num,0,sizeof(num)); memset(dp,0,sizeof(dp)); } int main() { int n; while(scanf("%d",&n),n) { clear(); int x,y; for(int i=1;i<=n;i++) { scanf("%d %d",&x,&y); num[x][y]++; } for(int i=1;i<=100;i++) for(int j=1;j<=100;j++) dp[i][j] = max(dp[i-1][j],dp[i][j-1]) + num[i][j]; printf("%d\n",dp[100][100]); } puts("*"); return EXIT_SUCCESS; }

最长上升子序列LIS集合 POJ2533，POJ1631,POJ1887,POJ1609(二)