题目大意：如何留下最多的桥使其不相交

这个题看起来很麻烦，读懂了之后其实是让你求最长上升子序列

用动态规划求解

dp[i]表示长度为i的上升子序列的第i个元素的最小值

 

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 using namespace std; 5  6 int dp[40002]; 7 int n; 8  9 int main(int argc, char const *argv[])10 {11     int t;12     freopen("input.txt","r",stdin);13     scanf("%d",&t);14     while(t--) {15         scanf("%d",&n);16         int cnt = 0;17         while(n--) {18             int tmp;19             scanf("%d",&tmp);20             if(cnt == 0 || tmp > dp[cnt]) {21                 cnt++;22                 dp[cnt] = tmp;23             }24             else {25                 int p = lower_bound(dp, dp+cnt+1, tmp) - dp;26                 dp[p] = tmp;27             }28         }29         printf("%d\n",cnt);30     }    31     return 0;32 }
       
      
     

另外,lower_bound()为二分搜索的库函数，返回不小于tmp的指针