Задача

Смугу висотою $3$ см і шириною $n$ см суцільно заповнено прямокутниками $3 \times 1$ та $1 \times 3$ см. Скількома способами можна її заповнити? Різні способи – це різні кількості вказаних прямокутників та їх різні розташування.

Вхідні дані	Вихідні дані
1	1
5	4
12	60
50	122106097

Вхідні дані

Вихідні дані

122106097

Код № 1

import java.util.Scanner;

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

import java.util.Scanner;

class Main {

public static void main (String[] args) {

Scanner sc = new Scanner(System.in);

int n = sc.nextInt();

int[] F = new int[51];

F[0] = 0;

F[1] = 1;

F[2] = 1;

F[3] = 2;

F[4] = 3;

for(int i = 5; i <= n; i++) {

F[i] = F[i-2] + F[i-3] + F[i-4];

}

System.out.println(F[n]);

}

Рішення 1

Це завдання на динамічне програмування, тому спочатку нам потрібно розбити цю задачу на декілька простих. Треба порахувати кількість способів для чотирьох перших елементів масиву. Якщо рахувати далі, то ми помітимо, що кожне наступне значення отримується за формулою F[i] = F[i-2] + F[i-3] + F[i-4].

Код № 2

import java.util.Scanner;

public class Main {
	public static int[] F = new int[51];
	public static int numberOfWays(int n){
		F[0] = 0;
		F[1] = 1;
		F[2] = 1;
		F[3] = 2;
		F[4] = 3;
	    if(F[n] > 0) {
    		return F[n];
		} else {
    		F[n] = numberOfWays(n-2) + numberOfWays(n-3) + numberOfWays(n-4);
		}
		return F[n];
	}
	public static void main (String[] args){
	    Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
	    System.out.println(numberOfWays(n));
	}
}

import java.util.Scanner;

public class Main {

public static int[] F = new int[51];

public static int numberOfWays(int n){

F[0] = 0;

F[1] = 1;

F[2] = 1;

F[3] = 2;

F[4] = 3;

if(F[n] > 0) {

return F[n];

} else {

F[n] = numberOfWays(n-2) + numberOfWays(n-3) + numberOfWays(n-4);

}

return F[n];

}

public static void main (String[] args){

Scanner sc = new Scanner(System.in);

int n = sc.nextInt();

System.out.println(numberOfWays(n));

}

Рішення 2

Також для рішення цієї задачі можна використати рекурсію. При виклику функції ми перевіряємо, чи є в пам’яті це значення. Якщо такого значення не має, то ми його рахуємо. Таким чином ми уникаємо використання зайвої пам’яті.

Условие

В старых играх можно столкнуться с такой ситуацией. Герой прыгает по платформам, висящим в воздухе. Он должен перебраться от одного края экрана до другого. При прыжке с платформы на соседнюю у героя уходит $|y_{2} — y_{1}|$ энергии, где $y_{1}$ и $y_{2}$ — высоты, на которых расположены эти платформы. Кроме того, есть суперприём, позволяющий перескочить через платформу, но на это затрачивается $3\cdot\left|y_{2} — y_{1}\right|$ энергии.

Известны высоты платформ в порядке от левого края до правого. Найдите минимальное количество энергии, достаточное, чтобы добраться с $1$-ой платформы до $n$-ой (последней) и список (последовательность) платформ, по которым нужно пройти.

Входные данные

Первая строка содержит количество платформ $n (2 \leqslant n \leqslant 100000)$, вторая $n$ целых чисел, значения которых не превышают по модулю $400$ — высоты платформ.

Выходные данные

В первой строке выведите минимальное количество энергии. Во второй — количество платформ, по которым нужно пройти, а в третьей выведите список этих платформ.

Тесты

№	Ввод	Вывод
1	4 1 2 3 30	29 4 1 2 3 4
2	2 7 23	16 2 1 2
3	5 0 1 0 1 0	0 3 1 3 5

Код

import java.util.Scanner;

class Main{
	public static void main (String[] args) {
		final int MAX = 100001;
		Scanner sc = new Scanner(System.in);
        int amount_of_pltf = sc.nextInt();
        int[] energy, platforms,  list_of_pltf;
        int[] heights = new int[MAX];
        for (int i = 1; i <= amount_of_pltf; i++) heights[i] = sc.nextInt();
        
        energy = new int[MAX];
        platforms = new int[MAX];
        energy[1] = 0;
    	energy[2] = Math.abs(heights[2] - heights[1]);
    	platforms[1] = -1;
    	platforms[2] = 1;
    	
    	//В цикле вычисляем значения ячеек energy[j] и platforms[j](3 ≤ j ≤ amount_of_pltf)
	    for (int j = 3; j <= amount_of_pltf; j++){
	        if((energy[j-1] + Math.abs(heights[j] - heights[j-1])) < (energy[j-2] + 3 * Math.abs(heights[j] - heights[j-2]))){
	            energy[j] = energy[j-1] + Math.abs(heights[j] - heights[j-1]);
	            platforms[j] = j - 1;
	        } else {
	            energy[j] = energy[j-2] + 3 * Math.abs(heights[j] - heights[j-2]);
	            platforms[j] = j - 2;
	        }
	    }
	    
	    //В переменной final_amount вычисляем конечное количество платформ, по которым нужно пройти.
	    int final_amount = 0;
	    list_of_pltf = new int[MAX];
	    for (int l = amount_of_pltf; l > 0; l = platforms[l]) list_of_pltf[final_amount++] = l;
	    
    	System.out.println(energy[amount_of_pltf] + "\n" + final_amount);
	    for(int k = final_amount - 1; k >= 0; k--) System.out.print(list_of_pltf[k] + " ");
	}
}

import java.util.Scanner;

class Main{

public static void main (String[] args) {

final int MAX = 100001;

Scanner sc = new Scanner(System.in);

int amount_of_pltf = sc.nextInt();

int[] energy, platforms, list_of_pltf;

int[] heights = new int[MAX];

for (int i = 1; i <= amount_of_pltf; i++) heights[i] = sc.nextInt();

energy = new int[MAX];

platforms = new int[MAX];

energy[1] = 0;

energy[2] = Math.abs(heights[2] - heights[1]);

platforms[1] = -1;

platforms[2] = 1;

//В цикле вычисляем значения ячеек energy[j] и platforms[j](3 ≤ j ≤ amount_of_pltf)

for (int j = 3; j <= amount_of_pltf; j++){

if((energy[j-1] + Math.abs(heights[j] - heights[j-1])) < (energy[j-2] + 3 * Math.abs(heights[j] - heights[j-2]))){

energy[j] = energy[j-1] + Math.abs(heights[j] - heights[j-1]);

platforms[j] = j - 1;

} else {

energy[j] = energy[j-2] + 3 * Math.abs(heights[j] - heights[j-2]);

platforms[j] = j - 2;

}

//В переменной final_amount вычисляем конечное количество платформ, по которым нужно пройти.

int final_amount = 0;

list_of_pltf = new int[MAX];

for (int l = amount_of_pltf; l > 0; l = platforms[l]) list_of_pltf[final_amount++] = l;

System.out.println(energy[amount_of_pltf] + "\n" + final_amount);

for(int k = final_amount - 1; k >= 0; k--) System.out.print(list_of_pltf[k] + " ");

}

Решение

Для решения данной задачи используем несколько массивов для хранения значений затраченной энергии и подсчета платформ. Начнём с энергии. По условию у нас есть два приема для прыжка с одной платформы на другую:

Прыжок с платформы на соседнюю. Затрачивается $|y_{2} — y_{1}|$ энергии. В дальнейшем для упрощения этот вид прыжка будет называться «обычным».
Суперприём — прыжок, позволяющий перескочить через платформу. В этом случае затрачивается $3·|y_{2} — y_{1}|$ энергии. Далее по тексту этот прием будет называться «суперпрыжок».

Нам необходимо проверить какой прием эффективнее. Для этого мы сравниваем сумму затраченной энергии при «обычных» прыжках с первой платформы до третей, с энергией, затраченной при «суперпрыжке» с первой сразу на третью. Этот алгоритм мы рассматриваем для каждой платформы, начиная с $3$ и до последней. Последнее значение, которое мы получим в ходе применения наиболее выгодного приема, и будет являться минимальным количеством энергии.

Параллельно подсчету энергии необходимо нумеровать платформы, на которые мы прыгнули. Опять же, если «суперпрыжок» с первой на третью оказался выгоднее, чем «обычные» прыжки с первой до третей, то третья платформа окажется второй по счету, на которую мы прыгнули. Продолжая эти рассуждения мы подсчитываем нужные нам платформы.

Чтобы вывести список платформ, по которым мы прошли, мы записываем в новый массив номера платформ начиная с последнего значения массива platforms[amount_of_pltf]. Там же, с помощью счетчика считаем общее количество платформ.

java@Cat

Учебные материалы по изучению основ языка програvмирования Java

Author Archives: Анна Цивинская

e-olimp 8536. Заповнення смуги $3 \times n$

Задача

Вхідні дані

Вихідні дані

Тести

Код № 1

Рішення 1

Код № 2

Рішення 2

Посилання

e-olymp 798. Платформы

Условие

Входные данные

Выходные данные

Тесты

Код

Решение

Ссылки