DAG转移，从切题的数量来看是一道水题，给你n个棒，大的可以延续小的，问最少上升子序列的个数。
其实这道题是用贪心来写的，因为这是个有向无环图，到达分叉口，每一条路都要便历，所以每条路应该一样对待，有两维限制，可以先对其中一维进行排序，然后根据第二维的情况进行处理。
for循环：
#include<cstdio> #include<algorithm> #include<cmath> #include<iostream> #include<cstring> using namespace std; int n; struct node { int u,v; }big[5005]; bool vis[5005]; bool cmp(node a,node b) { if(a.u<b.u) return 1; else if(a.u==b.u&&a.v<b.v) return 1; return 0; } int main() { //freopen("input.txt","r",stdin); int cas; cin>>cas; while(cas--) { cin>>n; for(int i=0;i<n;i++) { cin>>big[i].u>>big[i].v; } sort(big,big+n,cmp); int ans=0; int t=0; memset(vis,0,sizeof(vis)); for(int i=0;i<n;i++) { if(vis[i]) continue; vis[i]=1; t=big[i].v; ans++; for(int j=i+1;j<n;j++) { if(big[j].v>=t&&vis[j]==0) { t=big[j].v; vis[j]=1; } } } printf("%d ",ans); } }
记忆化dfs贪心：
#include<cstdio> #include<algorithm> #include<cmath> #include<iostream> #include<cstring> using namespace std; int n; struct node { int u,v; }big[5005]; bool vis[5005]; bool cmp(node a,node b) { if(a.u<b.u) return 1; else if(a.u==b.u&&a.v<b.v) return 1; return 0; } void dfs(int x) { if(vis[x]) return; vis[x]=1; for(int j=x+1;j<n;j++) { if(vis[j]==0&&big[j].v>=big[x].v) { dfs(j); break;//记忆化贪心的时候要加上break； } } } int main() { //freopen("input.txt","r",stdin); int cas; cin>>cas; while(cas--) { cin>>n; for(int i=0;i<n;i++) { cin>>big[i].u>>big[i].v; } sort(big,big+n,cmp); int ans=0; memset(vis,0,sizeof(vis)); for(int i=0;i<n;i++) { if(!vis[i]) { dfs(i); ans++; } } printf("%d ",ans); } }