[Algorithm]Boj 2422 cpp

9429 ワード
白駿 ブルトポス algorithm アルゴリズム#アルゴリズム# 白駿2422 boj 2422 bruteforce テキストリンク

  • 2422


  • アイスクリームの種類N、避けるべき組み合わせ数M個.

  • 次は避けるべき2つのアイスクリームの組み合わせです.

    に答える



  • すべての可能なアイスクリームの組み合わせを回します(完全ナビゲーション)

  • 避けるべき組み合わせを全部回して、避けるべき組み合わせがあれば終わりです.

  • 避けなければならないすべての組み合わせが通過したら、countを増やします.

  • 上記の方法で行うとタイムアウトが発生します.

  • 200 199*198*10000=788億

  • では、何が減るのでしょうか.

  • すべてのアイスクリームを確認しなければなりません.私たちはできるだけ数えなければならないからです.

  • これはcheckの低演算量を減らす必要がありますが、この2つの組合せをどのように組み合わせて有意義な方法で格納し、同時に迅速に行うのでしょうか.

  • 私の場合、最初はpairで実現しました.

  • 配列は考慮されていません.1次元配列に現れると、避ける必要のない組合せがcheckを通過できない可能性があります.

  • しかし、2次元配列とは思わなかった.2 D配列を使用すれば、速度はすぐに実現できます.

  • 避けるべき組み合わせが昇順に入らない可能性があることに注意してください.

  • したがって、2次元配列の行(左)よりも大きい位置に列(右)を加えれば昇順で加味でき、可能であればアイスクリームの組み合わせを回して昇順で加味すれば正確に比較できる.

    コード#コード#

    #include <iostream>
#include <vector>

using namespace std;

int check_list[200][200];

int check(int i, int j, int k)
{
	if (check_list[i][j] != 1 && check_list[j][k] != 1
			&& check_list[i][k] != 1)
		return (1);
	return (0);
}

int run(int N)
{
	int count = 0;
	for (int i = 0; i < N - 2; i++)
		for (int j = i + 1; j < N - 1; j++)
			for (int k = j + 1; k < N; k++)
				if (check(i, j, k))
					count++;
	return (count);
}

int main(void)
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int N, M;
	vector<pair<int, int> > sep;

	cin >> N >> M;
	for (int i = 0; i < M; i++)
	{
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		if (a < b)
			check_list[a][b] = 1;
		else
			check_list[b][a] = 1;
	}
	cout << run(N) << endl;
}
    • GoFデザインモード)Factory Method Pattern
    bootstrap tableクリックイベントの追加