wrzesień 2019 – Lazy spot

00001 – Grudki złota – Programowanie dynamiczne

Treść zadania:

Na planszy o wymiarach n na m rozrzucone są grudki złota. Po planszy chodzi robocik, który może zbierać grudki lecz porusza się tylko od prawej do lewej lub od lewej do prawej. Robocik może wykonać ruch o jedno pole w prawo lub jeżeli jest to możliwe o jedno pole po skosie w prawo do góry lub po skosie w prawo i do dołu.

Wejście:
Na wejściu zostaną podane dwie liczby w oddzielnych liniach oznaczająe szerokość (x) oraz wysokość (y) planszy, po której porusza się robocik. Następinie zostanie podane x wieszy w których znajduje się y liczb oznaczających ilość grudek na każdym polu

Wyjście
Na wyjściu ma znaleźć się maksymalna liczba grudek, które może zebrać robocik

Zakres danych:
3 ⩽ n ⩽ 1000
3 ⩽ m ⩽ 1000

Przykład:

Wejście:
5
5
1 3 3 2 1
2 1 4 3 1
0 6 4 0 0
2 3 4 0 2
4 1 0 4 4

Wyjście:
20

Program generujący testy do zadania:

#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <fstream>

using namespace std;
int main() {
	int a, b;	
	ofstream file;
	file.open("test.txt");
	cin >> a >> b;
	file << a << " " << b << "\n";
	for (int i = 0; i < a; i++) {
		for (int j = 0; j < b; j++) {
			file << rand() % 11 << " ";
		}
		file << "\n";
	}
	file.close();
}

Rozwiązanie bez użycia programowania dynamicznego:

#include <iostream>
#include <algorithm>

using namespace std;

const static int tab_max_size = 1000;
int input_tab[tab_max_size][tab_max_size];
int dp[tab_max_size][tab_max_size];
int n, m;
int solve(int x, int y) {
	int sum = 0;
	if (y == 0) {
		return input_tab[x][y];
	}
	if (x > 0) {
		sum = input_tab[x][y] + solve(x - 1, y - 1);
	}
	sum = max(sum, input_tab[x][y] + solve(x, y - 1));
	if (x < m) {
		sum = max(sum, input_tab[x][y] + solve(x + 1, y - 1));
	}
	return sum;
}

int main() {
	int output=0;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> input_tab[i][j];
		}
	}
	cin.get();
	for (int i = 0; i < m; i++) {
		output = max(solve(i, n),output);
	}
	/*for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cout << input_tab[i][j];
		}
		cout << endl;
	}*/
	cout << output << endl;
	cin.get();
}

Rozwiązania z użyciem programowania dynamicznego:

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const static int tab_max_size = 1000;
int input_tab[tab_max_size][tab_max_size];
int dp[tab_max_size][tab_max_size];
int n, m;
int solve(int x, int y) {
	int sum = 0;
	if (y == 0) {
		return input_tab[x][y];
	}
	if (dp[x][y] != -1) {
		return dp[x][y];
	}
	if (x > 0) {
		sum = input_tab[x][y] + solve(x - 1, y - 1);
	}
	sum = max(sum, input_tab[x][y] + solve(x, y - 1));
	if (x < m) {
		sum = max(sum, input_tab[x][y] + solve(x + 1, y - 1));
	}
	dp[x][y] = sum;
	return sum;
}

int main() {
	int output = 0;
	memset(dp, -1, sizeof(dp));
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> input_tab[i][j];
		}
	}
	cin.get();
	for (int i = 0; i < m; i++) {
		output = max(solve(i, n),output);
	}
	cout << output << endl;
	cin.get();
}

Kod źródłwy dostępny na GiHubie: https://github.com/lazyspot/Algorithms