nyoj 16矩形ネスト(DAG上のダイナミックプランニング)
3025 ワード
長方形のネスト
時間制限:
3000 ms|メモリ制限:
65535 KB
難易度:
4
説明
長さと幅を表すn個の矩形があり、各矩形はa,bで記述することができる.矩形X(a,b)は、矩形Y(c,d)にネストすることができ、a入力
1行目は正の数N(0各試験データの最初の行は正の数nであり、この試験データのセットに矩形の個数が含まれていることを示す(n<=1000)
その後のn行は,各行に2つの数a,b(0しゅつりょく
テストデータのセットごとに1つの数を出力し、最大条件を満たす矩形の数を表し、各グループの出力は1行を占めます.
サンプル入力
サンプル出力
タイトルリンク:http://acm.nyist.edu.cn/JudgeOnline/problem.php?pid=16
経典のテーマ、ダイナミックな計画を勉強して、頑張っています.
解法一:再帰
d(i)は、矩形iからの最長シーケンス長を表す.劉汝佳の「アルゴリズムコンテスト入門経典」を参考にする.
解法二:プッシュ
d(i)は、末尾が矩形iの最長長であることを示す
繰返しは再帰的に直接変更することはできません.矩形の配列には前後の順序がないので、直接前後にはできません.d(i)の計算が終わった後、d(i)を押し出したdが変わる可能性があるので、d(i)が間違っています.
そこで矩形を処理し,長いエッジをl(length),短いエッジをw(weight)とし,その後lを小さいものから大きいものに並べ替える必要がある.これにより、後方へのプッシュ時から、プッシュされたdが以降のプッシュ中に変化しないことを保証することができる.
時間制限:
3000 ms|メモリ制限:
65535 KB
難易度:
4
説明
長さと幅を表すn個の矩形があり、各矩形はa,bで記述することができる.矩形X(a,b)は、矩形Y(c,d)にネストすることができ、a
1行目は正の数N(0
その後のn行は,各行に2つの数a,b(0
テストデータのセットごとに1つの数を出力し、最大条件を満たす矩形の数を表し、各グループの出力は1行を占めます.
サンプル入力
1
10
1 2
2 4
5 8
6 10
7 9
3 1
5 8
12 10
9 7
2 2
サンプル出力
5タイトルリンク:http://acm.nyist.edu.cn/JudgeOnline/problem.php?pid=16
経典のテーマ、ダイナミックな計画を勉強して、頑張っています.
解法一:再帰
d(i)は、矩形iからの最長シーケンス長を表す.劉汝佳の「アルゴリズムコンテスト入門経典」を参考にする.
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct rect{
int l, w;
};
rect rec[1010];
int d[1010];
int n;
int dp(int i) {
int& ans = d[i];
if(ans > 0) return ans;
ans = 1;
int j;
for(j = 1; j <= n; j++) {
if( rec[j].l > rec[i].l && rec[j].w > rec[i].w ||
rec[j].w > rec[i].l && rec[j].l > rec[i].w) {
ans = max(ans, dp(j) + 1);
}
}
return ans;
}
int main() {
int N;
scanf("%d", &N);
while(N--) {
scanf("%d", &n);
int i;
for(i = 1; i <= n; i++) {
scanf("%d %d", &rec[i].l, &rec[i].w);
}
int maxn = 0;
memset(d, 0, sizeof(d)); //
for(i = 1; i <= n; i++) { //
if(maxn < dp(i)) maxn = d[i];
}
printf("%d
", maxn);
}
return 0;
} 解法二:プッシュ
d(i)は、末尾が矩形iの最長長であることを示す
繰返しは再帰的に直接変更することはできません.矩形の配列には前後の順序がないので、直接前後にはできません.d(i)の計算が終わった後、d(i)を押し出したdが変わる可能性があるので、d(i)が間違っています.
そこで矩形を処理し,長いエッジをl(length),短いエッジをw(weight)とし,その後lを小さいものから大きいものに並べ替える必要がある.これにより、後方へのプッシュ時から、プッシュされたdが以降のプッシュ中に変化しないことを保証することができる.
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct rect{
int l, w;
};
rect rec[1010];
int d[1010];
int n;
int cmp(rect a, rect b) {
return a.l < b.l;
}
int main() {
int N;
scanf("%d", &N);
while(N--) {
scanf("%d", &n);
int i, j;
for(i = 1; i <= n; i++) {
scanf("%d %d", &rec[i].l, &rec[i].w);
if(rec[i].l < rec[i].w) {
int t = rec[i].l;
rec[i].l = rec[i].w;
rec[i].w = t;
}
}
int maxn = 1;
for(i = 1; i <= n; i++) {
d[i] = 1;
}
sort(rec + 1, rec + n + 1, cmp);
for(i = 1; i <= n; i++) {
for(j = i - 1; j >= 1; j--) {
if( rec[i].l > rec[j].l && rec[i].w > rec[j].w) {
d[i] = max(d[i], d[j]+ 1);
}
}
if(maxn < d[i]) maxn = d[i];
}
printf("%d
", maxn);
}
return 0;
}