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