这道题不就是最长不下降子序列,建议回去看看
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
#define kb 5010
struct Edge{
int from, to;
}E[kb];
int dp[kb];
bool map[kb][kb];
bool cmp(Edge a, Edge b)
{
if(a.from>b.from)
return false;
else
return true;
}
int main()
{
int n, u, v;
scanf("%d", &n);
for(int i=1; i<=n; i++)
{
scanf("%d%d", &E[i].from, &E[i].to);
dp[i]=1;
}
sort(E+1, E+n+1, cmp);
for(int i=2; i<=n; i++)
for(int j=1; j<i; j++)
if(E[j].to<=E[i].to)
dp[i]=max(dp[i], dp[j]+1);
int max=0;
for(int i=1; i<=n; i++)
if(dp[i]>dp[max])
max=i;
printf("%d", dp[max]);
return 0;
}
emm,就是这个,我之前打的是sort不对好吧,不要复制