6 条题解

  • 1
    @ 2025-7-24 9:32:16
    #include<bits/stdc++.h>
    using namespace std;
    struct uuu
    {
    	long long x,y;
    };
    long long dp[5001];
    bool cmp(uuu a,uuu b)
    {
    	return a.x<b.x;
    }
    int main()
    {
    	long long n;
    	cin>>n>>n>>n;
    	uuu a[n+1];
    	for(long long i=1;i<=n;i++)
    	{
    		cin>>a[i].x>>a[i].y;
    		dp[i]=1;
    	}
    	sort(a+1,a+1+n,cmp);
    	long long maxn=0;
    	for(long long i=2;i<=n;i++)
    	{
    		for(long long j=1;j<i;j++)
    		{
    			if(a[i].y>a[j].y)
    			{
    				dp[i]=max(dp[i],dp[j]+1);
    				maxn=max(dp[i],maxn);
    			}
    		}
    	}
    	cout<<maxn;
    }
    
    • 0
      @ 2025-7-31 10:30:34
      using namespace std;
      const int N=2e5+10;
      int t,n,dp[N],x,y;
      int maxx;
      struct node{
      	int c,d;
      }a[N];
      bool cmp(node a1,node a2){
      	return a1.c<a2.c;
      }
      int main(){
      	cin>>x>>y;
      	cin>>n;
      	for(int i=1;i<=n;i++){
      		cin>>a[i].c>>a[i].d;
      	}
      	sort(a+1,a+n+1,cmp);
      	for(int i=1;i<=n;i++){
      		dp[i]=1;
      		for(int j=1;j<=i;j++){
      			if(a[i].d>a[j].d){
      				dp[i]=max(dp[i],dp[j]+1);
      			}
      			maxx=max(dp[i],maxx);
      		}
      	}
      	cout<<maxx;
      }
      
      
      
      
      
      
      
      
      • 0
        @ 2024-7-14 18:00:37
        #include<bits/stdc++.h>
        using namespace std;
        
        const int N=5e3+10;
        int n,dp[N],len,x,y;
        struct Friendly_City{
        	int k,l;
        }a[N];
        
        bool cmp(Friendly_City x,Friendly_City y)
        {
        	return x.k<y.k;
        }
        
        int main()
        {
        	cin>>x>>y;
        	scanf("%d",&n);
        	for(int i=1;i<=n;++i)
        	{
        		scanf("%d%d",&a[i].k,&a[i].l);
        	}
        	sort(a+1,a+n+1,cmp);
        	dp[++len]=a[1].l;
        	for(int i=1;i<=n;++i)
        	{
        		if(dp[len]<a[i].l)
        		{
        			dp[++len]=a[i].l;
        		}
        		else
        		{
        			int upd=upper_bound(dp+1,dp+len+1,a[i].l)-dp;
        			dp[upd]=a[i].l;
        		}
        	}
        	printf("%d",len);
        	return 0;
        }
        
        • 0
          @ 2023-4-1 15:13:26

          这题实际做起来不难,但是思路很恶心。

          比如说,一开始看到交叉瞬间不想做了,交叉是个啥?怎么做。

          思路:

          按照北岸排个序,接下来直接套LIS的模板即可

          #include<bits/stdc++.h>
          using namespace std;
          struct uuu
          {
          	long long x,y;
          };
          long long dp[5001];
          bool cmp(uuu a,uuu b)
          {
          	return a.x<b.x;
          }
          int main()
          {
          	long long n;
          	cin>>n>>n>>n;
          	uuu a[n+1];
          	for(long long i=1;i<=n;i++)
          	{
          		cin>>a[i].x>>a[i].y;
          		dp[i]=1;
          	}
          	sort(a+1,a+1+n,cmp);
          	long long maxn=0;
          	for(long long i=2;i<=n;i++)
          	{
          		for(long long j=1;j<i;j++)
          		{
          			if(a[i].y>a[j].y)
          			{
          				dp[i]=max(dp[i],dp[j]+1);
          				maxn=max(dp[i],maxn);
          			}
          		}
          	}
          	cout<<maxn;
          }
          
          • 0
            @ 2023-2-24 21:06:35

            P1229 友好城市

            看着这题,一脸懵逼:啥是交叉?可能只有我会一脸懵逼

            A    B
             \   |
              \  |
               \ | 
                \|
                 |
                 |\
                 | \
                 B  A
            

            如果有一条已经被批准的航道,它的南北坐标为N1,S1;

            则第二条N2<N1,S2>S1N2<N1,S2>S1的航道就会发生交叉。

            思路

            按北岸坐标大小对城市进行排序,来保证北岸序列单调上升,然后,南岸序列的最长上升子序列长度就是能够批准的航线条数。

            代码:

            #include <iostream>
            #include <algorithm>
            using namespace std;
            
            int ans,n,a[200001];
            
            struct tag
            {
            	int south,north;
            };
            tag c[200001];
            
            bool cmp(tag &a,tag &b)
            {
            	return a.south < b.south;
            }
            
            int main()
            {
            	cin >> n;
            	for(int i = 1;i <= n;i++)
            	{
            		cin >> c[i].south >> c[i].north;
            	}
            	sort(c + 1,c + n + 1,cmp);//排序south
            	for(int i = 1;i <= n;i++)
            	{
            		if(a[ans] < c[i].north)
            		{
            			a[++ans] = c[i].north;
            		}
            		else
            		{
            			*lower_bound(a + 1,a + ans + 1,c[i].north) = c[i].north;
            		}
            	}
            	cout << ans;
            	return 0;
            }
            
            • -1
              @ 2025-7-24 9:29:28
              #include <algorithm>
              #include <bitset>
              #include <cctype>
              #include <cerrno>
              #include <clocale>
              #include <cmath>
              #include <complex>
              #include <cstdio>
              #include <cstdlib>
              #include <cstring>
              #include <ctime>
              #include <deque>
              #include <exception>
              #include <fstream>
              #include <functional>
              #include <limits>
              #include <list>
              #include <map>
              #include <iomanip>
              #include <ios>
              #include <iosfwd>
              #include <iostream>
              #include <istream>
              #include <ostream>
              #include <queue>
              #include <set>
              #include <sstream>
              #include <stack>
              #include <stdexcept>
              #include <streambuf>
              #include <string>
              #include <utility>
              #include <vector>
              #include <cwchar>
              #include <cwctype>
              #include <complex.h>
              #include <fenv.h>
              #include <inttypes.h>
              #include <stdbool.h>
              #include <stdint.h>
              #include <tgmath.h>
              #include <stdio.h>
              #include <string.h>
              #include <math.h>
              #include <algorithm>
              #include <bitset>
              #include <cctype>
              #include <cerrno>
              #include <clocale>
              #include <cmath>
              #include <complex>
              #include <cstdio>
              #include <cstdlib>
              #include <cstring>
              #include <ctime>
              #include <deque>
              #include <exception>
              #include <fstream>
              #include <functional>
              #include <limits>
              #include <list>
              #include <map>
              #include <iomanip>
              #include <ios>
              #include <iosfwd>
              #include <iostream>
              #include <istream>
              #include <ostream>
              #include <queue>
              #include <set>
              #include <sstream>
              #include <stack>
              #include <stdexcept>
              #include <streambuf>
              #include <string>
              #include <utility>
              #include <vector>
              #include <cwchar>
              #include <cwctype>
              #include <complex.h>
              #include <fenv.h>
              #include <inttypes.h>
              #include <stdbool.h>
              #include <stdint.h>
              #include <tgmath.h>
              #include <stdio.h>
              #include <string.h>
              #include <math.h>
              #include <algorithm>
              #include <bitset>
              #include <cctype>
              #include <cerrno>
              #include <clocale>
              #include <cmath>
              #include <complex>
              #include <cstdio>
              #include <cstdlib>
              #include <cstring>
              #include <ctime>
              #include <deque>
              #include <exception>
              #include <fstream>
              #include <functional>
              #include <limits>
              #include <list>
              #include <map>
              #include <iomanip>
              #include <ios>
              #include <iosfwd>
              #include <iostream>
              #include <istream>
              #include <ostream>
              #include <queue>
              #include <set>
              #include <sstream>
              #include <stack>
              #include <stdexcept>
              #include <streambuf>
              #include <string>
              #include <utility>
              #include <vector>
              #include <cwchar>
              #include <cwctype>
              #include <complex.h>
              #include <fenv.h>
              #include <inttypes.h>
              #include <stdbool.h>
              #include <stdint.h>
              #include <tgmath.h>
              #include <stdio.h>
              #include <string.h>
              #include <math.h>
              #include <algorithm>
              #include <bitset>
              #include <cctype>
              #include <cerrno>
              #include <clocale>
              #include <cmath>
              #include <complex>
              #include <cstdio>
              #include <cstdlib>
              #include <cstring>
              #include <ctime>
              #include <deque>
              #include <exception>
              #include <fstream>
              #include <functional>
              #include <limits>
              #include <list>
              #include <map>
              #include <iomanip>
              #include <ios>
              #include <iosfwd>
              #include <iostream>
              #include <istream>
              #include <ostream>
              #include <queue>
              #include <set>
              #include <sstream>
              #include <stack>
              #include <stdexcept>
              #include <streambuf>
              #include <string>
              #include <utility>
              #include <vector>
              #include <cwchar>
              #include <cwctype>
              #include <complex.h>
              #include <fenv.h>
              #include <inttypes.h>
              #include <stdbool.h>
              #include <stdint.h>
              #include <tgmath.h>
              #include <stdio.h>
              #include <string.h>
              #include <math.h>
              #include <algorithm>
              #include <bitset>
              #include <cctype>
              #include <cerrno>
              #include <clocale>
              #include <cmath>
              #include <complex>
              #include <cstdio>
              #include <cstdlib>
              #include <cstring>
              #include <ctime>
              #include <deque>
              #include <exception>
              #include <fstream>
              #include <functional>
              #include <limits>
              #include <list>
              #include <map>
              #include <iomanip>
              #include <ios>
              #include <iosfwd>
              #include <iostream>
              #include <istream>
              #include <ostream>
              #include <queue>
              #include <set>
              #include <sstream>
              #include <stack>
              #include <stdexcept>
              #include <streambuf>
              #include <string>
              #include <utility>
              #include <vector>
              #include <cwchar>
              #include <cwctype>
              #include <complex.h>
              #include <fenv.h>
              #include <inttypes.h>
              #include <stdbool.h>
              #include <stdint.h>
              #include <tgmath.h>
              #include <stdio.h>
              #include <string.h>
              #include <math.h>
              #include <algorithm>
              #include <bitset>
              #include <cctype>
              #include <cerrno>
              #include <clocale>
              #include <cmath>
              #include <complex>
              #include <cstdio>
              #include <cstdlib>
              #include <cstring>
              #include <ctime>
              #include <deque>
              #include <exception>
              #include <fstream>
              #include <functional>
              #include <limits>
              #include <list>
              #include <map>
              #include <iomanip>
              #include <ios>
              #include <iosfwd>
              #include <iostream>
              #include <istream>
              #include <ostream>
              #include <queue>
              #include <set>
              #include <sstream>
              #include <stack>
              #include <stdexcept>
              #include <streambuf>
              #include <string>
              #include <utility>
              #include <vector>
              #include <cwchar>
              #include <cwctype>
              #include <complex.h>
              #include <fenv.h>
              #include <inttypes.h>
              #include <stdbool.h>
              #include <stdint.h>
              #include <tgmath.h>
              #include <stdio.h>
              #include <string.h>
              #include <math.h>
              #include <algorithm>
              #include <bitset>
              #include <cctype>
              #include <cerrno>
              #include <clocale>
              #include <cmath>
              #include <complex>
              #include <cstdio>
              #include <cstdlib>
              #include <cstring>
              #include <ctime>
              #include <deque>
              #include <exception>
              #include <fstream>
              #include <functional>
              #include <limits>
              #include <list>
              #include <map>
              #include <iomanip>
              #include <ios>
              #include <iosfwd>
              #include <iostream>
              #include <istream>
              #include <ostream>
              #include <queue>
              #include <set>
              #include <sstream>
              #include <stack>
              #include <stdexcept>
              #include <streambuf>
              #include <string>
              #include <utility>
              #include <vector>
              #include <cwchar>
              #include <cwctype>
              #include <complex.h>
              #include <fenv.h>
              #include <inttypes.h>
              #include <stdbool.h>
              #include <stdint.h>
              #include <tgmath.h>
              #include <stdio.h>
              #include <string.h>
              #include <math.h>
              #include <algorithm>
              #include <bitset>
              #include <cctype>
              #include <cerrno>
              #include <clocale>
              #include <cmath>
              #include <complex>
              #include <cstdio>
              #include <cstdlib>
              #include <cstring>
              #include <ctime>
              #include <deque>
              #include <exception>
              #include <fstream>
              #include <functional>
              #include <limits>
              #include <list>
              #include <map>
              #include <iomanip>
              #include <ios>
              #include <iosfwd>
              #include <iostream>
              #include <istream>
              #include <ostream>
              #include <queue>
              #include <set>
              #include <sstream>
              #include <stack>
              #include <stdexcept>
              #include <streambuf>
              #include <string>
              #include <utility>
              #include <vector>
              #include <cwchar>
              #include <cwctype>
              #include <complex.h>
              #include <fenv.h>
              #include <inttypes.h>
              #include <stdbool.h>
              #include <stdint.h>
              #include <tgmath.h>
              #include <stdio.h>
              #include <string.h>
              #include <math.h>
              #include <algorithm>
              #include <bitset>
              #include <cctype>
              #include <cerrno>
              #include <clocale>
              #include <cmath>
              #include <complex>
              #include <cstdio>
              #include <cstdlib>
              #include <cstring>
              #include <ctime>
              #include <deque>
              #include <exception>
              #include <fstream>
              #include <functional>
              #include <limits>
              #include <list>
              #include <map>
              #include <iomanip>
              #include <ios>
              #include <iosfwd>
              #include <iostream>
              #include <istream>
              #include <ostream>
              #include <queue>
              #include <set>
              #include <sstream>
              #include <stack>
              #include <stdexcept>
              #include <streambuf>
              #include <string>
              #include <utility>
              #include <vector>
              #include <cwchar>
              #include <cwctype>
              #include <complex.h>
              #include <fenv.h>
              #include <inttypes.h>
              #include <stdbool.h>
              #include <stdint.h>
              #include <tgmath.h>
              #include <stdio.h>
              #include <string.h>
              #include <math.h>
              #include <algorithm>
              #include <bitset>
              #include <cctype>
              #include <cerrno>
              #include <clocale>
              #include <cmath>
              #include <complex>
              #include <cstdio>
              #include <cstdlib>
              #include <cstring>
              #include <ctime>
              #include <deque>
              #include <exception>
              #include <fstream>
              #include <functional>
              #include <limits>
              #include <list>
              #include <map>
              #include <iomanip>
              #include <ios>
              #include <iosfwd>
              #include <iostream>
              #include <istream>
              #include <ostream>
              #include <queue>
              #include <set>
              #include <sstream>
              #include <stack>
              #include <stdexcept>
              #include <streambuf>
              #include <string>
              #include <utility>
              #include <vector>
              #include <cwchar>
              #include <cwctype>
              #include <complex.h>
              #include <fenv.h>
              #include <inttypes.h>
              #include <stdbool.h>
              #include <stdint.h>
              #include <tgmath.h>
              #include <stdio.h>
              #include <string.h>
              #include <math.h>
              #include <algorithm>
              #include <bitset>
              #include <cctype>
              #include <cerrno>
              #include <clocale>
              #include <cmath>
              #include <complex>
              #include <cstdio>
              #include <cstdlib>
              #include <cstring>
              #include <ctime>
              #include <deque>
              #include <exception>
              #include <fstream>
              #include <functional>
              #include <limits>
              #include <list>
              #include <map>
              #include <iomanip>
              #include <ios>
              #include <iosfwd>
              #include <iostream>
              #include <istream>
              #include <ostream>
              #include <queue>
              #include <set>
              #include <sstream>
              #include <stack>
              #include <stdexcept>
              #include <streambuf>
              #include <string>
              #include <utility>
              #include <vector>
              #include <cwchar>
              #include <cwctype>
              #include <complex.h>
              #include <fenv.h>
              #include <inttypes.h>
              #include <stdbool.h>
              #include <stdint.h>
              #include <tgmath.h>
              #include <stdio.h>
              #include <string.h>
              #include <math.h>
              #include <algorithm>
              #include <bitset>
              #include <cctype>
              #include <cerrno>
              #include <clocale>
              #include <cmath>
              #include <complex>
              #include <cstdio>
              #include <cstdlib>
              #include <cstring>
              #include <ctime>
              #include <deque>
              #include <exception>
              #include <fstream>
              #include <functional>
              #include <limits>
              #include <list>
              #include <map>
              #include <iomanip>
              #include <ios>
              #include <iosfwd>
              #include <iostream>
              #include <istream>
              #include <ostream>
              #include <queue>
              #include <set>
              #include <sstream>
              #include <stack>
              #include <stdexcept>
              #include <streambuf>
              #include <string>
              #include <utility>
              #include <vector>
              #include <cwchar>
              #include <cwctype>
              #include <complex.h>
              #include <fenv.h>
              #include <inttypes.h>
              #include <stdbool.h>
              #include <stdint.h>
              #include <tgmath.h>
              #include <stdio.h>
              #include <string.h>
              #include <math.h>
              #include <algorithm>
              #include <bitset>
              #include <cctype>
              #include <cerrno>
              #include <clocale>
              #include <cmath>
              #include <complex>
              #include <cstdio>
              #include <cstdlib>
              #include <cstring>
              #include <ctime>
              #include <deque>
              #include <exception>
              #include <fstream>
              #include <functional>
              #include <limits>
              #include <list>
              #include <map>
              #include <iomanip>
              #include <ios>
              #include <iosfwd>
              #include <iostream>
              #include <istream>
              #include <ostream>
              #include <queue>
              #include <set>
              #include <sstream>
              #include <stack>
              #include <stdexcept>
              #include <streambuf>
              #include <string>
              #include <utility>
              #include <vector>
              #include <cwchar>
              #include <cwctype>
              #include <complex.h>
              #include <fenv.h>
              #include <inttypes.h>
              #include <stdbool.h>
              #include <stdint.h>
              #include <tgmath.h>
              #include <stdio.h>
              #include <string.h>
              #include <math.h>
              #include <algorithm>
              #include <bitset>
              #include <cctype>
              #include <cerrno>
              #include <clocale>
              #include <cmath>
              #include <complex>
              #include <cstdio>
              #include <cstdlib>
              #include <cstring>
              #include <ctime>
              #include <deque>
              #include <exception>
              #include <fstream>
              #include <functional>
              #include <limits>
              #include <list>
              #include <map>
              #include <iomanip>
              #include <ios>
              #include <iosfwd>
              #include <iostream>
              #include <istream>
              #include <ostream>
              #include <queue>
              #include <set>
              #include <sstream>
              #include <stack>
              #include <stdexcept>
              #include <streambuf>
              #include <string>
              #include <utility>
              #include <vector>
              #include <cwchar>
              #include <cwctype>
              #include <complex.h>
              #include <fenv.h>
              #include <inttypes.h>
              #include <stdbool.h>
              #include <stdint.h>
              #include <tgmath.h>
              #include <stdio.h>
              #include <string.h>
              #include <math.h>
              #include <algorithm>
              #include <bitset>
              #include <cctype>
              #include <cerrno>
              #include <clocale>
              #include <cmath>
              #include <complex>
              #include <cstdio>
              #include <cstdlib>
              #include <cstring>
              #include <ctime>
              #include <deque>
              #include <exception>
              #include <fstream>
              #include <functional>
              #include <limits>
              #include <list>
              #include <map>
              #include <iomanip>
              #include <ios>
              #include <iosfwd>
              #include <iostream>
              #include <istream>
              #include <ostream>
              #include <queue>
              #include <set>
              #include <sstream>
              #include <stack>
              #include <stdexcept>
              #include <streambuf>
              #include <string>
              #include <utility>
              #include <vector>
              #include <cwchar>
              #include <cwctype>
              #include <complex.h>
              #include <fenv.h>
              #include <inttypes.h>
              #include <stdbool.h>
              #include <stdint.h>
              #include <tgmath.h>
              #include <stdio.h>
              #include <string.h>
              #include <math.h>
              #include <algorithm>
              #include <bitset>
              #include <cctype>
              #include <cerrno>
              #include <clocale>
              #include <cmath>
              #include <complex>
              #include <cstdio>
              #include <cstdlib>
              #include <cstring>
              #include <ctime>
              #include <deque>
              #include <exception>
              #include <fstream>
              #include <functional>
              #include <limits>
              #include <list>
              #include <map>
              #include <iomanip>
              #include <ios>
              #include <iosfwd>
              #include <iostream>
              #include <istream>
              #include <ostream>
              #include <queue>
              #include <set>
              #include <sstream>
              #include <stack>
              #include <stdexcept>
              #include <streambuf>
              #include <string>
              #include <utility>
              #include <vector>
              #include <cwchar>
              #include <cwctype>
              #include <complex.h>
              #include <fenv.h>
              #include <inttypes.h>
              #include <stdbool.h>
              #include <stdint.h>
              #include <tgmath.h>
              #include <stdio.h>
              #include <string.h>
              #include <math.h>
              #include <algorithm>
              #include <bitset>
              #include <cctype>
              #include <cerrno>
              #include <clocale>
              #include <cmath>
              #include <complex>
              #include <cstdio>
              #include <cstdlib>
              #include <cstring>
              #include <ctime>
              #include <deque>
              #include <exception>
              #include <fstream>
              #include <functional>
              #include <limits>
              #include <list>
              #include <map>
              #include <iomanip>
              #include <ios>
              #include <iosfwd>
              #include <iostream>
              #include <istream>
              #include <ostream>
              #include <queue>
              #include <set>
              #include <sstream>
              #include <stack>
              #include <stdexcept>
              #include <streambuf>
              #include <string>
              #include <utility>
              #include <vector>
              #include <cwchar>
              #include <cwctype>
              #include <complex.h>
              #include <fenv.h>
              #include <inttypes.h>
              #include <stdbool.h>
              #include <stdint.h>
              #include <tgmath.h>
              #include <stdio.h>
              #include <string.h>
              #include <math.h>
              #include <algorithm>
              #include <bitset>
              #include <cctype>
              #include <cerrno>
              #include <clocale>
              #include <cmath>
              #include <complex>
              #include <cstdio>
              #include <cstdlib>
              #include <cstring>
              #include <ctime>
              #include <deque>
              #include <exception>
              #include <fstream>
              #include <functional>
              #include <limits>
              #include <list>
              #include <map>
              #include <iomanip>
              #include <ios>
              #include <iosfwd>
              #include <iostream>
              #include <istream>
              #include <ostream>
              #include <queue>
              #include <set>
              #include <sstream>
              #include <stack>
              #include <stdexcept>
              #include <streambuf>
              #include <string>
              #include <utility>
              #include <vector>
              #include <cwchar>
              #include <cwctype>
              #include <complex.h>
              #include <fenv.h>
              #include <inttypes.h>
              #include <stdbool.h>
              #include <stdint.h>
              #include <tgmath.h>
              #include <stdio.h>
              #include <string.h>
              #include <math.h>
              #include <algorithm>
              #include <bitset>
              #include <cctype>
              #include <cerrno>
              #include <clocale>
              #include <cmath>
              #include <complex>
              #include <cstdio>
              #include <cstdlib>
              #include <cstring>
              #include <ctime>
              #include <deque>
              #include <exception>
              #include <fstream>
              #include <functional>
              #include <limits>
              #include <list>
              #include <map>
              #include <iomanip>
              #include <ios>
              #include <iosfwd>
              #include <iostream>
              #include <istream>
              #include <ostream>
              #include <queue>
              #include <set>
              #include <sstream>
              #include <stack>
              #include <stdexcept>
              #include <streambuf>
              #include <string>
              #include <utility>
              #include <vector>
              #include <cwchar>
              #include <cwctype>
              #include <complex.h>
              #include <fenv.h>
              #include <inttypes.h>
              #include <stdbool.h>
              #include <stdint.h>
              #include <tgmath.h>
              #include <stdio.h>
              #include <string.h>
              #include <math.h>
              #include <algorithm>
              #include <bitset>
              #include <cctype>
              #include <cerrno>
              #include <clocale>
              #include <cmath>
              #include <complex>
              #include <cstdio>
              #include <cstdlib>
              #include <cstring>
              #include <ctime>
              #include <deque>
              #include <exception>
              #include <fstream>
              #include <functional>
              #include <limits>
              #include <list>
              #include <map>
              #include <iomanip>
              #include <ios>
              #include <iosfwd>
              #include <iostream>
              #include <istream>
              #include <ostream>
              #include <queue>
              #include <set>
              #include <sstream>
              #include <stack>
              #include <stdexcept>
              #include <streambuf>
              #include <string>
              #include <utility>
              #include <vector>
              #include <cwchar>
              #include <cwctype>
              #include <complex.h>
              #include <fenv.h>
              #include <inttypes.h>
              #include <stdbool.h>
              #include <stdint.h>
              #include <tgmath.h>
              #include <stdio.h>
              #include <string.h>
              #include <math.h>
              using namespace std;
              const int N=1e4+10;
              const int INF=0x3f3f3f3f;
              int x,y,n,dp[N],maxn;
              struct node{
              	int sta,end;
              }a[N];
              bool cmp(node a1,node a2)
              {
              	return a1.sta<a2.sta;
              }
              int main()
              {
              	cin>>x>>y>>n;
              	for(int i=1;i<=n;i++)
              		cin>>a[i].sta>>a[i].end;
              	sort(a+1,a+n+1,cmp);
              	
              	for(int i=1;i<=n;i++){
              		dp[i]=1;
              		for(int j=1;j<i;j++)
              			if(a[i].end>a[j].end)
              				dp[i]=max(dp[i],dp[j]+1);
              		maxn=max(maxn,dp[i]);
              	}
              	cout<<maxn;	
              	return 0;
              }
              
              
              
              • 1

              信息

              ID
              1722
              时间
              1000ms
              内存
              256MiB
              难度
              7
              标签
              递交数
              578
              已通过
              142
              上传者