ブルトポス

ブルトポス

アルゴリズム

は、すべての場合に

を試みることができる.

ブルートフォードでは、最も重要なのは状況の総数がいくらなのかを事前に知ることです.

低音砲は、数が少ない場合にのみ使用できます.

ステージ

題の可能性を計算してみましょう.

は、可能なすべての方法を試みる.

for文

シーケンス

回校コール★

ビットマスク

それぞれの方法で答えを解く.

時間の複雑さ

=O(メソッドの数x試行の複雑さ)

ステップ1

計算インスタンス数

•N人がずらりと並んだ人数→N!(N<=10)
•N人から代表2人を選ぶ→O(N^2)
•N人から代表3人を選ぶ→O(N^3)
•N人の中から班長1名と副班長1名を選ぶ→O(N^2)
•N人がいると、誰もが映画を見ないことにします.可能な組み合わせ数→O(2^N)
->N番は1人に2つの選択肢があるので、22・・=2 Nを乗せればよい(N<=20)

質問1)2309番7人の小人

質問する

王妃を避けるため、7人の小人と平和に暮らしていた白雪姫は危機に直面した.一日の仕事を終えて帰ってきた矮人は7人ではなく、9人だった.
9人の小人はみな「白雪姫と7人の小人」の主役だと主張している.優れた数学的直感を持つ白雪姫は、幸いにも7人の小人の身長の和が100だったことを覚えている.
9人のジュニアの身長を手に入れたとき、白雪姫に7人のジュニアを探すプログラムを書いてください.

入力

9列の小人の身長.与えられた身長は100を超えない自然数で、9人のジュニアの身長はすべて異なっていて、可能な答えがたくさんあれば、勝手に出力することができます.

しゅつりょく

昇順に7人の小人の身長を出力する.7人の小人が見つからないことはない.

入力例1

20
7
23
19
10
15
25
8
13

サンプル出力1

7
8
10
13
19
20
23

私の実施

順番が何であれ7つ先に引く.
組み合わせ100のみをアレイに入れ、最後に入れた組み合わせが出力されます

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
	static int[] answer;
	static void combination(int[] arr, boolean[] visited, int start, int n, int r) {
		if (r == 0) {
			print(arr, visited, n);
			return;
		}

		for (int i = start; i < n; i++) {
			visited[i] = true;
			combination(arr, visited, i + 1, n, r - 1);
			visited[i] = false;
		}
	}

	// 배열 출력
	static void print(int[] arr, boolean[] visited, int n) {
		StringBuilder sb = new StringBuilder();
		int[] temp = new int[7];
		int sum = 0;
		int index=0;
		for (int i = 0; i < n; i++) {
			if (visited[i]) {
				sum+=arr[i];
				temp[index] = arr[i];
				index++;
			}
		}
		if(sum==100)
		{
			answer = Arrays.copyOf(temp, temp.length);
			return;
		}
		return;
	}
	public static void main(String[] args) throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int count = 0;
		int N = 9;
		int[] arr = new int[N];
		answer = new int[7];
		boolean[] visited= new boolean[N];
		for(int i=0; i<N;i++)
			arr[i] = Integer.parseInt(reader.readLine());
		combination(arr, visited,0,N,7);
		Arrays.sort(answer);
		for(int num : answer)
			sb.append(num+"\n");
		System.out.println(sb);
	}

}

講義

私は9つの中から7つを選び、仁康で
9人の中で2人を選ぶ人はあまりいないからです.
二人を選んだほうがいい
=>メソッド数:N^2
•ジュニアの数がNの場合
•二人を選ぶ場合の数:N^2.
•他のジュニアの身長の和を選ぶ時間の複雑さ:O(N)
•したがって、この問題はO(N^3)で解決できる.
でもO(n^2)で解くこともできます.
背の低い人は変わらない
1.すべてのジュニアの八卦箱を保存する
2.i,j(9人中2人少ない)
sum-A[i]-A[j] == 100 => O(1)

問題2）3085キャンディゲーム

質問する

尚根は子供の頃、「Bomboni」ゲームが好きだった.
最初はN×砂糖をnサイズのところに入れる.キャンディの色が違うかもしれません.上根は隣接するキャンディの色の異なる格子を2つ選んだ.それから均一な四角い格子の中のキャンディを交換します.今では、すべての人が同じ色からなる最長の連続部分(行または列)を選択し、すべてのキャンディを食べてしまいます.
あなたがあなたにあげた砂糖が満たされたとき、プログラムを書いて、あなたが食べられる砂糖の最大個数を求めます.

入力

最初の行は、プレートのサイズNを与える.(3 ≤ N ≤ 50)
次のN行は、板紙に充填されたキャンディの色を与える.赤はC、青はP、緑はZ、黄色はYです.
隣接する2つのキャンディ色の異なる格子が存在する入力のみが与えられる.

しゅつりょく

1行目は、食べられるキャンディの最大個数を出力します.

入力例1

5
YCPZY
CYZZP
CCPPP
YCYZC
CPPZZ

サンプル出力1

4

プロセス

• N×Nサイズのテーブルにキャンディがあります.(N ≤ 50)
•隣接する2つの部屋を選び、キャンディを交換する
->まず1つのセルを選択し、そのセルの4つの隣接するセルのうちのもう1つを表示します.
->1つのセルを選択してN^2 x 4(隣接する4つのセル)=O(N^2)
•同じ色の最長連続部分の行または列を選択する問題
->すべての長さをチェックする必要がある->O(N^2)
=>O(N^4)->50^4=2500^2=6250000=>

インプリメンテーション

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	static char[][] arr;

	public static void swap(int i, int j, int ii, int jj) {
		char temp = arr[i][j];
		arr[i][j] = arr[ii][jj];
		arr[ii][jj] = temp;
	}
	 static int check(char[][] a, int start_row, int end_row, int start_col, int end_col) {
	        int n = a.length;
	        int ans = 1;
	        for (int i=start_row; i<=end_row; i++) {
	            int cnt = 1;
	            for (int j=1; j<n; j++) {
	                if (a[i][j] == a[i][j-1]) {
	                    cnt += 1;
	                } else {
	                    cnt = 1;
	                }
	                if (ans < cnt) ans = cnt;
	            }
	        }
	        for (int i=start_col; i<=end_col; i++) {
	            int cnt = 1;
	            for (int j=1; j<n; j++) {
	                if (a[j][i] == a[j-1][i]) {
	                    cnt += 1;
	                } else {
	                    cnt = 1;
	                }
	                if (ans < cnt) ans = cnt;
	            }
	        }
	        return ans;
	    }

	public static void main(String[] args) throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int N = Integer.parseInt(reader.readLine());
		// NxN
		long max = -999;
		int temp_num=0;
		arr = new char[N][N];
		for (int i = 0; i < N; i++)
			arr[i] = reader.readLine().trim().toCharArray();

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (j + 1 < N) {
					swap(i, j, i, j + 1);
					temp_num = check(arr, i, i, j, j+1);;
					if (max<temp_num)
						max=temp_num;
					swap(i, j, i, j + 1);
				}
				if (i + 1 < N) {
					swap(i, j, i + 1, j);
					temp_num = check(arr, i, i+1, j, j);;
					if (max<temp_num)
						max=temp_num;
					swap(i, j, i + 1, j);
				}
			}
		}
		System.out.println(max);
	}
}