嵌套模型（DAG上的动态规划）—动态规划入门（算法经典入门）
矩形嵌套3000 ms | 内存限制：65535 KB#include <iostream>#include <string.h>#include <cstdio>using namespace std;int G[1010][1010];int d[1010];int n;int dp(int i) { int &ans=d[i]; if(ans>0) return ans; //记忆化 ans=1; for(int j=1; j<=n; j++) { if(G[i][j]) { if(ans < dp(j) + 1) { ans = dp(j)+1; } } } return ans;}void print_ans(int i){ printf("%d ",i); for(int j=1;j<=n;j++) { if(G[i][j]&&d[i]==d[j]+1){ print_ans(j); break; } }}void print_map(){ for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { cout << G[i][j] << ' '; } cout << endl; }}int main(){ int N; scanf("%d", &N); while(N--){ int a[1010], b[1010]; memset(G, 0, sizeof(G)); memset(d, 0, sizeof(d)); scanf("%d", &n); for(int i=1;i<=n;i++) { scanf("%d%d", &a[i], &b[i]); } for(int i=1; i<=n; i++) { for(int j=1;j<=n; j++) { if((a[i]>a[j]&&b[i]>b[j])||(a[i]>b[j]&&b[i]>a[j])) { G[i][j]=1; ///建图,有向无环图。 } } } //print_map(); int max1 = 0; //int max_i = 0; for(int i=1; i<=n; i++) { if(dp(i) > max1) { max1=dp(i); // max_i = i; } } // print_ans(max_i); // cout << endl; cout<<max1<<endl; } return 0;}/*******************************http://acm.nyist.edu.cn/JudgeOnline/status.php?pid=16*******************************/
