アルゴリズムベース2/1-401

401-動的プログラミング1(練習)

1,2,3に3-15988を加える

私の答え

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

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[] input = new int[n + 1];
		for (int i = 1; i < input.length; i++) {
			input[i] = Integer.parseInt(br.readLine());
		}
		long[] dp = new long[1000001];
		int mod = 1000000009;
		dp[1] = 1;
		dp[2] = 2;
		dp[3] = 4;
		for (int i = 4; i < dp.length; i++) {
			dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3]) % mod;
		}
		for (int i = 1; i < input.length; i++) {
			System.out.println(dp[input[i]]);
		}
	}
}

2つのドアで開くとタイムアウトするので、dp配列は持つことができる最大値を求め、入力した数字をそれぞれ出力します.
400問の答えは同じです.省略してください.

RGB距離-1149

私の答え

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

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[][] input = new int[n + 1][3];
		for (int i = 1; i < input.length; i++) {
			String[] temp = br.readLine().split(" ");
			for (int j = 0; j < input[0].length; j++) {
				input[i][j] = Integer.parseInt(temp[j]);
			}
		}
		int[][] dp = new int[n + 1][3];
		dp[1][0] = input[1][0];
		dp[1][1] = input[1][1];
		dp[1][2] = input[1][2];
		for (int i = 1; i < input.length; i++) {
			dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + input[i][0];
			dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + input[i][1];
			dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]) + input[i][2];
		}
		System.out.println(Math.min(dp[n][0], Math.min(dp[n][1], dp[n][2])));
	}
}

簡単に言えば、横で繰り返しができない条件の下で、対角線で和を求める場合、費用の最小の和をその位置に置いて、同じ方法で最後まで行います.では、最後の3つ(96、172、185)に最小費用を出力する.

動物園-1309

私の答え

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

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[][] dp = new int[n + 1][3];
		int mod = 9901;
		dp[1][0] = 1;
		dp[1][1] = 1;
		dp[1][2] = 1;
		for (int i = 2; i < dp.length; i++) {
			dp[i][0] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % mod;
			dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % mod;
			dp[i][2] = (dp[i - 1][0] + dp[i - 1][1]) % mod;
		}
		System.out.println((dp[n][0] + dp[n][1] + dp[n][2]) % mod);
	}
}

上の図のように、前の行が何であるか(左にあるか、右にあるか、ないか)によって、次の行が来ることができる場合に数を加えればよい.点火式は以下の通り
dp[n][空白]=dp[n-1][空白]+dp[n-1][左]+dp[n-1][右]
dp[n][左]=dp[n-1][空白]+dp[n-1][右]
dp[n][右]=dp[n-1][空白]+dp[n-1][左]
または
dp[n] = dp[n - 1] * 2 + dp[n-2]

上り坂-1157

私の答え

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

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int mod = 10007;
		long[][] dp = new long[n + 1][10];
		for (int i = 0; i < dp[0].length; i++) {
			dp[1][i] = 1;
		}
		for (int i = 2; i < dp.length; i++) {
			for (int j = 0; j < dp[0].length; j++) {
				for (int k = j; k < dp[0].length; k++) {
					dp[i][j] += (dp[i - 1][k]);
				}
				dp[i][j] %= mod;
			}
		}
		long answer = 0;
		for (int i = 0; i < dp[0].length; i++) {
			answer += dp[n][i];
			answer %= mod;
		}
		System.out.println(answer);
	}
}

N=2の場合,前位数が0から9に増加すると,状況の数は減少する.
また、最前面(0の場合)であれば、0の後の数はN=1に等しい.
そのため、点火式は以下の通りです.
dp[n][0] = dp[n-1][0~9]
dp[n][1] = dp[n-1][1~9]
dp[n][2] = dp[n-1][2~9]
...
dp[n][9] = dp[n-1][9]
そこで,dp[n][0~9]の値を求めるために,三重for文で求める.
または
dp[n][m] = dp[n-1][m] + dp[n][m-1]

シール-9465

私の答え

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

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		for (int i = 0; i < n; i++) {
			int m = Integer.parseInt(br.readLine());
			int[][] dp = new int[3][m + 1];
			int[][] input = new int[3][m + 1];
			for (int j = 1; j < input.length; j++) {
				String[] temp = br.readLine().split(" ");
				for (int k = 1; k < input[0].length; k++) {
					input[j][k] = Integer.parseInt(temp[k - 1]);
				}
			}
			dp[1][1] = input[1][1];
			dp[2][1] = input[2][1];
			for (int j = 2; j < input[0].length; j++) {
				dp[1][j] = Math.max(dp[2][j - 1], dp[2][j - 2]) + input[1][j];
				dp[2][j] = Math.max(dp[1][j - 1], dp[1][j - 2]) + input[2][j];
			}
			System.out.println(Math.max(dp[1][m], dp[2][m]));
		}
	}
}

最初は最低価格の場合は3種類で計算していましたが、考えてみれば、1種類も必要ありません.点火式は以下の通り
dp[1][n] = max(dp[2][n-1], dp[2][n-2]) + input[1][n]
dp[2][n] = max(dp[1][n-1], dp[1][n-2]) + input[2][n]
ps.max値にはdp[1][n-2]も加わっているが、不要である.

ワイン試食-256

私の答え

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

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[] input = new int[n + 1];
		int[] dp = new int[n + 1];
		for (int i = 1; i < dp.length; i++) {
			input[i] = Integer.parseInt(br.readLine());
		}
		dp[1] = input[1];
		if (n > 1) {
			dp[2] = input[1] + input[2];
		}
		for (int i = 3; i < dp.length; i++) {
			dp[i] = Math.max(dp[i - 3] + input[i - 1] + input[i], Math.max(dp[i - 2] + input[i], dp[i - 1]));
		}
		System.out.println(dp[n]);
	}
}

3つのコップについて、数に応じて点火式を確立したのは以下の通りである.
dp[n] = dp[n-3] + input[i-1] + input[i]
dp[n] = dp[n-2] + input[i]
dp[n] = dp[n-1]
上記3つの場合、水中最大の値を選択します.

整数三角形-132

私の答え

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

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[][] input = new int[n + 1][n + 1];
		for (int i = 1; i < input.length; i++) {
			String[] temp = br.readLine().split(" ");
			for (int j = 1; j <= i; j++) {
				input[i][j] = Integer.parseInt(temp[j - 1]);
			}
		}
		int[][] dp = new int[n + 1][n + 1];
		dp[1][1] = input[1][1];
		for (int i = 2; i < dp.length; i++) {
			for (int j = 1; j < dp.length; j++) {
				if (j == 1) {
					dp[i][j] = dp[i - 1][j];
				} else if (i == j) {
					dp[i][j] = dp[i - 1][j - 1];
				} else {
					dp[i][j] = Math.max(dp[i - 1][j - 1], dp[i - 1][j]);
				}
				dp[i][j] += input[i][j];
			}
		}
		int answer = 0;
		for (int i = 1; i < dp.length; i++) {
			answer = Math.max(answer, dp[n][i]);
		}
		System.out.println(answer);
	}
}

上からの累積和を求めればいい.生きたいなら、以下の3つを選ぶことができます.
ケース1:一番左
case 2:右端
Case 3:その他(中間)
点火式は以下の通り.
case 1: dp[n][m] = dp[n - 1][m]
dp[n][m] = dp[n - 1][m - 1]
dp[n][m] = max(dp[n - 1][m - 1], dp[n - 1][m]);

最大増分数列-11055

私の答え

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

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[] input = new int[n + 1];
		String[] temp = br.readLine().split(" ");
		for (int i = 1; i < input.length; i++) {
			input[i] = Integer.parseInt(temp[i - 1]);
		}
		int[] dp = new int[n + 1];
		int answer = dp[1];
		for (int i = 1; i < dp.length; i++) {
			dp[i] = input[i];
			for (int j = 1; j < i; j++) {
				if (input[i] > input[j]) {
					dp[i] = Math.max(dp[i], dp[j] + input[i]);
				}
			}
			answer = Math.max(answer, dp[i]);
		} 
		System.out.println(answer);
	}
}

最も長く成長した部分数列と同じであるが,dp[n]値をinput[n]に初期化する必要がある点が異なる.値段はもちろん違うので...
(インクリメンタル部分数列で1秒初期化…)
点火式は次の通りです
dp[n] = max(dp[n], dp[m] + input[i])

最も長い減少部分-11722

私の答え

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

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[] input = new int[n + 1];
		String[] temp = br.readLine().split(" ");
		for (int i = 1; i < input.length; i++) {
			input[i] = Integer.parseInt(temp[i - 1]);
		}
		int[] dp = new int[n + 1];
		int answer = 1;
		for (int i = 1; i < dp.length; i++) {
			dp[i] = 1;
			for (int j = 1; j < i; j++) {
				if (input[i] < input[j]) {
					dp[i] = Math.max(dp[i], dp[j] + 1);
				}
			}
			answer = Math.max(dp[i], answer);
		}
		System.out.println(answer);
	}
}

プールは最大成長数列に等しいので省略してください
逆等号でいい

最長のバイナリ部分数列-11054

私の答え

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

public class Main {
	static int[] dpIn;
	static int[] dpDe;
	static int[] input;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		input = new int[n + 1];
		String[] temp = br.readLine().split(" ");
		for (int i = 1; i < input.length; i++) {
			input[i] = Integer.parseInt(temp[i - 1]);
		}
		dpIn = new int[n + 1];
		increase();
		dpDe = new int[n + 1];
		decrease();
		int answer = 0;
		for (int i = 1; i < dpIn.length; i++) {
			answer = Math.max(dpIn[i] + dpDe[i], answer); // 증가 수열과 감소 수열의 합
		}
		System.out.println(answer - 1);// 증가수열의 끝과 감소수열의 끝이 중복이므로
	}

	public static void increase() { // 앞에서부터 증가 수열
		for (int i = 1; i < dpIn.length; i++) {
			dpIn[i] = 1;
			for (int j = 1; j < i; j++) {
				if (input[i] > input[j]) {
					dpIn[i] = Math.max(dpIn[i], dpIn[j] + 1);
				}
			}
		}
	}

	public static void decrease() {// 뒤에서부터 감소 수열
		for (int i = dpDe.length - 1; i > 0; i--) {
			dpDe[i] = 1;
			for (int j = dpDe.length - 1; j > i; j--) {
				if (input[i] > input[j]) {
					dpDe[i] = Math.max(dpDe[i], dpDe[j] + 1);
				}
			}
		}
	}
}

もう一度言う
追加部分数列+減少部分数列-1(オーバーラップ部分)

連続2-3398

私の答え

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

public class Main {
	static int[] dpL;
	static int[] dpR;
	static int[] input;
	static int answer = Integer.MIN_VALUE;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		input = new int[n + 1];
		String[] temp = br.readLine().split(" ");
		for (int i = 1; i < input.length; i++) {
			input[i] = Integer.parseInt(temp[i - 1]);
		}
		dpL = new int[n + 1];
		dpR = new int[n + 1];
		dpR[n] = input[n];
		left();
		right();
		System.out.println(maxSum());
	}

	public static void left() {
		for (int i = 1; i < dpL.length; i++) {
			dpL[i] = Math.max(dpL[i - 1] + input[i], input[i]);
			answer = Math.max(answer, dpL[i]);
		}
	}

	public static void right() {
		for (int i = dpR.length - 2; i >= 0; i--) {
			dpR[i] = Math.max(dpR[i + 1] + input[i], input[i]);
//			System.out.println(dpR[i + 1]);
		}
	}

	public static int maxSum() {
		for (int i = 1; i < dpL.length - 1; i++) {
			answer = Math.max(answer, dpL[i - 1] + dpR[i + 1]);
		}
		return answer;
	}

}

タイル充填-233

私の答え

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

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[] dp = new int[n + 1];
		dp[0] = 1;
		for (int i = 2; i < dp.length; i += 2) {
			dp[i] = dp[i - 2] * 3;
			for (int j = i - 4; j >= 0; j -= 2) {
				dp[i] += dp[j] * 2;
			}
		}
		System.out.println(dp[n]);
	}
}

まず、Nが奇数の場合(幅を考慮)はあり得ない
だから偶数の場合だけ判断します.
デフォルトでは、N=2は通常3つのケースを有する.
上の図に示すように、n=2の場合、2つの組み合わせごとに9つの形状が現れる.
一方,Nの増加に伴い,2つの特異な形状(n=4から最後の2つの形状)が認められた.
そのため、点火式は以下の通りです.
dp[n] = (d[n-2]x3) + ([n-4]x2 + d[n-6]x2 + ... + d[0]x2)
デフォルトでは、dp[i]=dp[i-2]x 3->通常の外観
特殊形状nが大きいほどx 2
後で...がんばってください.