首页 > 代码库 > DAG镶嵌模型+原始路径打印
DAG镶嵌模型+原始路径打印
DP矩形镶嵌,打印路径与最长公共子序列相似。
1 #include<stdio.h> 2 #include<string.h> 3 #define doumax(a,b) (a>b?a:b) 4 const int maxn=100; 5 int mat[maxn][maxn],dp[maxn],n; 6 struct node{ 7 int a; 8 int b; 9 void dousort(void)10 {11 if(a<b){12 int temp=a;13 a=b;14 b=temp;15 }16 }17 bool operator<(const node & t)18 {19 return t.a>a && t.b>b;20 }21 void operator=(const node & t)22 {23 a=t.a;b=t.b;24 }25 }rect[maxn],rectinit[maxn];26 int dpmodel(int i);27 void print_road(int i);28 int main()29 {30 while(scanf("%d",&n)==1){31 for(int i=1;i<=n;i++){32 scanf("%d%d",&rect[i].a,&rect[i].b);33 rectinit[i]=rect[i];34 rect[i].dousort();35 }36 memset(mat,0,sizeof(mat));37 memset(dp,0,sizeof(dp));38 for(int i=1;i<=n;i++)39 for(int j=i+1;j<=n;j++){40 if(rect[i]<rect[j])41 mat[i][j]=1;42 else if(rect[j]<rect[i])43 mat[j][i]=1;44 }45 int maxroad=0,maxi;46 for(int i=1;i<=n;i++){47 if(maxroad<dpmodel(i)){48 maxroad=dpmodel(i);49 maxi=i;50 }51 }52 printf("%d\n",maxroad);53 print_road(maxi);54 }55 return 0;56 }57 int dpmodel(int i)58 {59 if(dp[i]>0)60 return dp[i];61 dp[i]=1;62 for(int j=1;j<=n;j++)63 if(mat[i][j])64 dp[i]=doumax(dp[i],dpmodel(j)+1);65 return dp[i];66 }67 void print_road(int i)68 {69 printf("(%d,%d)\n",rectinit[i].a,rectinit[i].b);70 if(dp[i]==1)71 return;72 for(int j=1;j<=n;j++)73 if(mat[i][j] && dp[i]==dp[j]+1){74 print_road(j);75 return;76 }77 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。