DAG上的动态规划之嵌套矩形

时间:2022-06-30 08:26:14

  题意描述:有n个矩形,每个矩形可以用两个整数a、b描述,表示它的长和宽,

       矩形(a,b)可以嵌套在矩形(c,d)当且仅当a<c且b<d,

       要求选出尽量多的矩形排成一排,使得除了最后一个外,

       每一个矩形都可以嵌套在下一个矩形内,如果有多解,矩形编号的字典序应尽量小

  解题思路:<1>矩形之间的可嵌套关系是一个"二元关系",二元关系可以用图来建模。

       如果矩形X可以嵌套在矩形Y里,就从X到Y连一条有向边(G[x][y]=1)。

       这个图是无环的,因为一个矩形无法直接或间接地嵌套在自己内部,

       换句话说,他是一个DAG。

       这样,原问题便转化为求DAG上的最长路径。

       <2>那么如何求DAG最长上的最长路径呢?

         可定义状态: dp[i]表示从结点i出发所能到达的最长路径的长度

         那么: dp[i] = max(dp[j]) + 1, 其中G[i][j]=1,即i可嵌套在j中

         最后数组d中的最大值便是结果

       <3>如何保证最小字典序?

         在所有的d都计算出来以后,选择最大的d[i]所对应的i。

         如果有多个i,选择最小的i。(i即第一个起点)

         接下来可以选择d[i] = d[j]+1且(i,j)为边集的任何一个j,

         但为了保证字典序最小,应该选择其中最小的j,

/* DAG上的动态规划之嵌套矩形 */
#include <cstdio>
#include <cstring> const int maxn = ;
int n, G[maxn][maxn];
int a[maxn], b[maxn];
int dp[maxn]; void swap(int &x, int &y){
x ^= y;
y ^= x;
x ^= y;
} //将x和y的最大值存在x中
inline void CMAX(int& x, int y){
if (y > x){
x = y;
}
} /* 采用记忆化搜索 求从s能到达的最长路径 */
int DP(int s){
int& ans = dp[s];
if (ans > )
//记忆化搜索,避免重复计算
return ans;
ans = ;
for (int j = ; j <= n; ++j){
if (G[s][j]){
//sj有边 利用子问题dp[j]+1更新最大值
CMAX(ans, DP(j) + );
}
}
return ans;
} void print_ans(int i){
printf("%d ", i);
for (int j = ; j <= n; ++j){
if (G[i][j] && dp[j] + == dp[i]){
print_ans(j);
break;
}
}//for(j)
} int main()
{
#ifdef _LOCAL
freopen("D:\\input.txt", "r", stdin);
#endif
while (scanf("%d", &n) == ){
//n个矩形
for (int i = ; i <= n; ++i){
//默认a存长,b存宽(a > b)
scanf("%d%d", a + i, b + i);
if (a[i] < b[i]){
swap(a[i], b[i]);
}
}
/*
建图 G[i][j]为1表示矩形i可以嵌套在矩形j中
那么原问题便转化为求DAG上的最长路径 定义状态dp[i]表示从结点i出发可以到达的最长路径
则 dp[i] = max(dp[j] + 1), 其中 G[i][j]=1,
*/
memset(G, , sizeof G);
for (int i = ; i <= n; ++i){
for (int j = ; j <= n; ++j){
//矩形i的长和宽都小于矩形j的长和宽
if (a[i] < a[j] && b[i] < b[j]){
G[i][j] = ; //可以嵌套,则有边
}
}
}//for(i)
memset(dp, , sizeof dp);
int ans = ;
int best;
for (int i = ; i <= n; ++i){
if (DP(i) > ans){
ans = dp[i];
best = i;
}
}//for(i)
printf("ans = %d\n", ans);
print_ans(best);
printf("\n");
}
return ;
}

  解题思路2:如果只需要求得最多可以嵌套多少个矩形,而不要求输出序列,

        定义一个结构体,内含有变量a,b,输入时保证a>b(a为长,b为宽)

        对a进行排序,最后求b的最长上升子序列(状态转移时要加上A[j].a<A[i].a的条件)

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; const int maxn = ;
int dp[maxn]; struct Node{
int a, b;
bool operator<(Node& other){
if (a != other.a){
return a < other.a;
}
else{
return b < other.b;
}
}
}A[maxn]; void SWAP(int& x, int& y){
x ^= y;
y ^= x;
x ^= y;
} void CMAX(int& x, int y){
if (y > x){
x = y;
}
} int main()
{
#ifdef _LOCAL
freopen("D:\\input.txt", "r", stdin);
#endif int n;
while (scanf("%d", &n) == ){
for (int i = ; i <= n; ++i){
//a为长,b为宽
scanf("%d%d", &A[i].a, &A[i].b);
if (A[i].a < A[i].b){
SWAP(A[i].a, A[i].b);
}
dp[i] = ;
}//for(i)
sort(A + , A + n + );
//求b的最长上升子序列
int ans = ;
int best = ;
dp[] = ;
for (int i = ; i <= n; ++i){
for (int j = ; j < i; ++j){
if (A[j].a < A[i].a && A[j].b < A[i].b){
CMAX(dp[i], dp[j] + );
}
}
if (dp[i] > ans){
ans = dp[i];
best = i;
}
//CMAX(ans, dp[i]);
} printf("ans = %d\n", ans);
} return ;
}