CJOJ 1070 【Uva】嵌套矩形（动态规划 图论）
Description
有 n 个矩形，每个矩形可以用两个整数 a, b 描述，表示它的长和宽。矩形 X(a, b) 可以嵌套在矩形 Y(c, d) 中当且仅当 a＜c, b＜d，或者 b＜c, a＜d（相当于把矩形 X 旋转了 90°）。例如 (1, 5) 可以嵌套在 (6, 2) 内，但不能嵌套在 (3, 4) 内。 你的任务是选出尽量多的矩形，使得除了最后一个之外，每一个矩形都可以嵌套在下一个矩形内。
第一行一个正整数 n (n <= 1000)。 接下来 n 行每行两个正整数 a, b 表示矩形 i 的长和宽。
Output
第一行一个整数 k 表示符合条件的最多矩形数。 第二行 k 个整数依次表示符合条件矩形的编号，要求字典序最小。
8 14 9 15 19 18 12 9 10 19 17 15 9 2 13 13 10
Sample Output
4 4 8 3 2
Http
CJOJ:http://oj.changjun.com.cn/problem/detail/pid/1070
Source
动态规划，图论
解决思路
这道题可以转化成图论问题。若有正方形A可以嵌套在正方形B中，我们就连一条边A->B，呢么这道题就转化成为求DAG（为什么是DAG呢，因为一个矩形不可能经过若干次嵌套后嵌套在自己里面，所以一定不会有环）上从任意一点出发的最长路径
我们令F[i]表示从i出发的最长路径，那么对于所有存在的路径i->j，一定有F[i]=max(F[j]+1)。由于初始起点不好计算（其实也可以计算，如用拓扑排序），为了方便期间，我们用记忆化搜索来实现。
为什么不令F[i]表示到i的最长路径呢？这样做虽然没错，但是最终输出路径时的解不一定是字典序（除非还用一个数组记录路径），因为在这里我们是用的从动归转移方程倒推路径。
，我们知道F[i]一定是从其能连到的一个点（假设是j）得到的，那么我们从１到n枚举，看是否满足F[i]=F[j]+1。因为我们是从小到大枚举的，又是正序输出，所以可以保证字典序。
代码
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxN=2000;
const int inf=2147483647;
int n;
int A[maxN];
int B[maxN];
int G[maxN][maxN];//用邻接矩阵存边
int F[maxN];//从i出发的最长路,F[i]为-１时表示还未访问
int dfs(int x);
void outp(int ans);
int main()
{
memset(F,-1,sizeof(F));
memset(G,-1,sizeof(G));
cin>>n;
for (int i=1;i<=n;i++)
{
cin>>A[i]>>B[i];
if (A[i]<B[i])
swap(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;
for (int i=1;i<=n;i++)
if (F[i]==-1)
F[i]=dfs(i);
/*cout<<"FFF"<<endl;
for (int i=1;i<=n;i++)
cout<<F[i]<<' ';
cout<<endl;*/
int Ans=0;
for (int i=1;i<=n;i++)
if (F[i]>F[Ans])
Ans=i;//找出最大值
cout<<F[Ans]<<endl;
outp(Ans);//倒推出方案
cout<<endl;
return 0;
}
int dfs(int x)//记忆化搜索
{
if (F[x]!=-1)//说明F[x]已经计算过了，直接返回
return F[x];
F[x]=1;
for (int i=1;i<=n;i++)
if (G[x][i]==1)//求出F[x]的最大值
F[x]=max(F[x],dfs(i)+1);
return F[x];
}
void outp(int ans)//倒推出解，但要注意是正序输出（因为我们定义的F[i]表示的是从i出发的最短路，所以推的时候是顺着最短路推的）
{
cout<<ans<<' ';
for (int i=1;i<=n;i++)
if ((G[ans][i]==1)&&(F[ans]==F[i]+1))
{
outp(i);
return;
}
return;
}
转载于:https://www.cnblogs.com/SYCstudio/p/7138157.html
相关资源：JAVA上百实例源码以及开源项目
