[珂苔]18-上り坂まで

1、2、3プラス3

整数nを1、2、3の和とする方法数を求める問題(n<=10000)

intに入ることができる数は約21億です.

d[]を宣言する場合は、intではなくlongとして宣言する必要があります.

コード#コード#

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc= new Scanner(System.in);
		long d[] = new long[1000001];
        //여기서 int대신 배열 d를 long으로 사용해야함!
		d[0]=1; //초기화
		for(int i=1;i<=1000000;i++) {
			for(int j=1; j<=3; j++) {	//1,2,3 
				if(i-j >= 0) {
					d[i] += d[i-j];
				}
			}
			d[i] %= 1000000009L;
		}
		int t = sc.nextInt();
		while(t-->0) {
			int n= sc.nextInt();
			System.out.println(d[n]);
		}
	}
}

RGB距離

RGB街に住んでいる人は、家を赤、緑、青のいずれかに塗っています.
そして、彼らはすべての隣人が同じ色を塗ることができないことを規定しています.
家iの隣人は家i-1と家i+1で、最初の家と最後の家は隣人ではありません.
最初の家と最後の家は隣人ではありません.
問題は、どの家にも赤塗りの費用、緑塗りの費用、青塗りの費用がある場合、すべての家の費用が最高値に達することだ.

A[i][j]:i号住宅をj号に塗装するコスト

家iの色がi-1と違うといいです(前の家と色が違うだけ)

隣家が続出する

連続した家は同じ色に塗ってはいけない.

D[i][j]=i号室を色jに塗った場合、1-i号室を塗る費用の最小値.
j=0->赤
j=1->緑
j=2->青
D[i][0] = min(D[i-1][1],D[i-1][2]) + A[i][0]
D[i][1] = min(D[i-1][0],D[i-1][2]) + A[i][1]
D[i][2] = min(D[i-1][0],D[i-1][1]) + A[i][2]
最後の家をどんな色に塗って記録しますか.
正解:min(D[N][0],D[N][1],D[N][2])

コード#コード#

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc= new Scanner(System.in);
		int n= sc.nextInt();
		int a[][]= new int [n+1][3];
		int d[][]= new int [n+1][3];
		
		for(int i=1;i<=n;i++) {
			for(int j=0;j<3;j++) {
				a[i][j]=sc.nextInt();
			}
		}
		
		for(int i=1;i<=n;i++) {
			d[i][0] = Math.min(d[i-1][1], d[i-1][2]) + a[i][0];
			d[i][1] = Math.min(d[i-1][0], d[i-1][2]) + a[i][1];
			d[i][2] = Math.min(d[i-1][0], d[i-1][1]) + a[i][2];
		}
		System.out.println(Math.min(Math.min(d[n][0], d[n][1]),d[n][2]));
		//d[n][0], d[n][1], d[n][2]중에 가장 작은 최소값을 구하는 문제.
	}
}

=>問題を解く前に、私は方法を考えるべきだと思います.アプローチの見方は簡単でわかりやすいですが、なかなか自分でアプローチするのは難しいようです…

n/a.動物園

動物園があり、横に2つ、縦にNつあります.
横に縦に置いてはいけません
可能な導入数は?
(1マス最大1本)
D[N]=垂直N間の動物園はレイアウトの数です.

の隣接領域を処理する必要があります.
D[N][M]=縦N格子を用いた動物園レイアウトの数、最後のマスM号の方法.

D[N][0]=Nは通じない.

D[N][1]=N番行の左側のみにあります.

D[N][2]=N番行の右側のみにあります.

そのため、

D[N][0] = D[N-1][0] + D[N-1][1] + D[N-1][2]
->N番行には置かれていないので、N-1には置かず、左または右のどちらでも構いません.

D[N][1] = D[N-1][0] + D[N-1][2]
->N行の左側に配置されているので、N-1を配置しないか、N-1の右側に配置しません.(N−1の左側は不可能であり、垂直に隣接するため)

D[N][2] = D[N-1][0] + D[N-1][1]
->N番はGUGの右側に置かれているので、N-1番を置かずに、N-1を左側に置くこともできます.(同様にN-1右側は不可能で垂直に隣接する)

コード#コード#

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc= new Scanner(System.in);
		int n= sc.nextInt();
		int d[][] = new int[n+1][3];
		
		d[0][0]=1;
		for(int i=1;i<=n;i++) {
			d[i][0] = d[i-1][0] + d[i-1][1] + d[i-1][2];
			d[i][1] = d[i-1][0] + d[i-1][2];
			d[i][2] = d[i-1][0] + d[i-1][1];
			for(int j=0;j<3;j++) {
				d[i][j] %= 9901;
			}
		}
		System.out.println( (d[n][0] + d[n][1] + d[n][2])%9901);
	}
}

上り坂

上り坂数とは、数字の位置が昇順に並ぶ数です.
隣接数は等しいが、昇順に打つ.
数の長さがNの時、上り坂の数の問題を求めます
数はゼロから始まることができます.
例:1233345357888815599

のような簡単な階段数の問題です.=>隣接位相差1

上り坂数=>隣接位置が順次上昇する.

D[i][j]=数の長さはi、最後(i)数はjの上り坂数の個数

i-1は来られるものがたくさんあるので変数を使いますk

上り坂数の桁が上昇順なのでk<=j.

D[i][j] += D[i-1][k] (0<=k<=j)

初期化

D[1][i]=1. (長さが1であるため)

D[1][0] = D[0][0]

D[1][1] = D[0][0] + D[0][1]

D[1][2] = D[0][0] + D[0][1] + D[0][2]
=>このように計算してもいずれも1なのでD[1][i]は1に初期化される.

コード#コード#

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc= new Scanner(System.in);
		int n= sc.nextInt();
		int d[][] = new int[n+1][10];
		//초기화해줌.
		for(int i=0;i<=9;i++) {
			d[1][i] = 1;
		}
		for(int i=2;i<=n;i++) {	//i가 1일 때 초기화했으니까 2부터 시작.
			for(int j=0;j<=9;j++) {  //j에 올 수 있는 숫자 10가지
				for(int k=0;k<=j;k++) {  //k는 j보다 작거나 같아야 함.
					d[i][j] += d[i-1][k];
					d[i][j] %= 10007;
				}
			}
		}
		long res=0;
		for(int i=0;i<10;i++) {
			res += d[n][i];
		}
		res %= 10007;
		System.out.println(res);
	}
}

これは崔伯俊先生のコードテストの基礎科目に基づいて書いた文章です.