DAGモデル
1722 ワード
【題意】
n個の矩形があり、各矩形には長さと幅があり、aとbとして表される.
矩形X(a,b)は、矩形Y(c,d)に嵌め込むことができ、a1つの中にネストできる最も多数を求めます
【考え方】
これはDPの一種で、まずソートして、検索する時に深さを記録して、ネストできる矩形を見つけた時に直接値を返します
時間複雑度O(n*n)
長方形の長さと幅は長さ>幅で並べます.
【コード】
n個の矩形があり、各矩形には長さと幅があり、aとbとして表される.
矩形X(a,b)は、矩形Y(c,d)に嵌め込むことができ、a
【考え方】
これはDPの一種で、まずソートして、検索する時に深さを記録して、ネストできる矩形を見つけた時に直接値を返します
時間複雑度O(n*n)
長方形の長さと幅は長さ>幅で並べます.
【コード】
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <algorithm>
#define N 100
using namespace std;
int dp[N];
int n;
struct matrix
{
int l,w;
}m[N];
bool cmp(matrix a, matrix b)
{
if(a.l != b.l) return a.l<b.l;
return a.w<b.w;
}
void DP()
{
int ans = 0;
for(int i=0; i<n; i++)
{
for(int j=0; j<i; j++)
{
if(m[j].l<m[i].l && m[j].w<m[i].w)
{
dp[i] = max(dp[i], dp[j]+1);
}
}
if(dp[i]==0) dp[i] = 1; // ，
ans = max(ans, dp[i]);
}
printf("%d
", ans);
}
int main()
{
while(1)
{
memset(dp, 0, sizeof(dp));
scanf("%d",&n);
if(n==0) break;
for(int i=0; i<n; i++)
{
scanf("%d%d",&m[i].l, &m[i].w);
if(m[i].l < m[i].w)
swap(m[i].l, m[i].w);
}
sort(m, m+n, cmp);
DP();
}
return 0;
}