質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

Q&A

解決済

1回答

2059閲覧

C++ DP、LIS問題について

bbdd

総合スコア43

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

0グッド

0クリップ

投稿2019/08/24 18:09

前提

C++

わからないこと

なぜ自分の回答が間違っているのか。
間違っていることはWAが発生していることからわかっているが、
どのようなテストケースにて失敗しているかの想像がつきませんでした。
教えて頂けますと幸いです。

対象の問題

こちらの問題です

atcoder

自分の回答

  • pair(w, h) に対してwの降順でsortし、次の要素がwとhが大きければ答えansに1を足す。
  • pair(w, h) に対してhの降順でsortし、次の要素がwとhが大きければ答えans2に1を足す。
  • ans, ans2の大きい方を答えとする
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> PII; typedef pair<ll, ll> PLL; #define EPS (1e-9) #define INF (1e9) #define INFL (1e18) #define MOD (1000000007) #define FOR(i, a, b) for (int i = (a); i < (b); ++i) #define REP(i, n) for (int i = 0; i < (n); ++i) #define ALL(obj) (obj).begin(), (obj).end() #define ALLR(obj) (obj).rbegin(), (obj).rend() #define BIT(n) (1LL << (n)) bool compare_by_b(pair<int, int> a, pair<int, int> b) { if(a.second != b.second){ return a.second < b.second; }else{ return a.first < b.first; } } int main() { ios::sync_with_stdio(false); cin.tie(0); int N; cin >> N; int w, h; vector<PII> v; vector<PII> v2; REP(i, N) { cin >> w >> h; v.push_back({w, h}); v2.push_back({w, h}); } sort(ALL(v)); sort(ALL(v2), compare_by_b); int ans = 1; int ans2 = 1; int boxw = v[0].first; int boxh = v[0].second; REP(i, N-1) { if ((boxw < v[i+1].first) && (boxh < v[i+1].second) ) { ++ ans; boxw = v[i+1].first; boxh = v[i+1].second; } } boxw = v2[0].first; boxh = v2[0].second; REP(i, N-1) { if ((boxw < v2[i+1].first) && (boxh < v2[i+1].second) ) { ++ ans2; boxw = v2[i+1].first; boxh = v2[i+1].second; } } if (ans >= ans2) { cout << ans; } else { cout << ans2; } }

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答1

0

ベストアンサー

まずは

どのようなテストケースにて失敗しているかの想像がつきませんでした。

の部分だけですが

N=6で
[0] = { .h = 1, .w = 100 },
[1] = { .h = 2, .w = 2 },
[2] = { .h = 3, .w = 3 },
[3] = { .h = 4, .w = 4 },
[4] = { .h = 5, .w = 5 },
[5] = { .h = 100, .w = 1 },

のようなデータである場合、

hによるソート結果からの演算では
[0]を使ってしまうようだと [0]のみで1重
[0]を無視できれば [1],[2],[3],[4],が使えて4重になります。
今のアルゴリズムだと前者の1重になります。

wによるソート結果からの演算では
[0] = { .h = 100, .w = 1 },
[1] = { .h = 2, .w = 2 },
[2] = { .h = 3, .w = 3 },
[3] = { .h = 4, .w = 4 },
[4] = { .h = 5, .w = 5 },
[5] = { .h = 1, .w = 100 },

[0]を使ってしまうと [0]のみで1重
[0]を無視できれば [1],[2],[3],[4],が使えて4重になります。
今のアルゴリズムだとこちらも前者の1重になります。

各要素を使う/使わないを仮定して最大になる組み合わせを求めるアルゴリズムが必要であると思います。

投稿2019/08/24 21:28

nomuken

総合スコア1627

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問