Riešenia (skupina A, 7. týždeň)

import java.util.Arrays;


public class Postupnost {

        public static int d(int i, int[] p) {
                System.out.println("Ratam d(" + i + ", ...)");
                int vysledok = 0;
                for (int j=0; j<i; j++)
                        if (p[j] < p[i])
                                vysledok = Math.max(vysledok, d(j, p));

                return 1 + vysledok;
        }

        public static int[] lis(int[] p) {
                int[] d = new int[p.length];
                int[] predchodzaVOptime = new int[p.length];

                for (int i=0; i<p.length; i++) {
                        int vysledok = 0;
                        predchodzaVOptime[i] = -1;
                        for (int j=0; j<i; j++)
                                if (p[j] < p[i]) {
                                        if (vysledok < d[j]) {
                                                vysledok = d[j];
                                                predchodzaVOptime[i] = j;
                                        }
                                }

                        d[i] = 1 + vysledok;
                }

                int maxDlzka = 0;
                int idxMaximalneho = 0;
                for (int i=0; i<d.length; i++) {
                        if (maxDlzka < d[i]) {
                                maxDlzka = d[i];
                                idxMaximalneho = i;
                        }
                }

                int[] vysledok = new int[maxDlzka];

                int aktualny = idxMaximalneho;
                for (int i=vysledok.length-1; i>=0; i--) {
                        vysledok[i] = p[aktualny];
                        aktualny = predchodzaVOptime[aktualny];
                }

                return vysledok;
        }


        /**
         * @param args
         */
        public static void main(String[] args) {
                int[] p = {5, 3, 1, 4, 6, 10, 8, 7};
                System.out.println(Arrays.toString(lis(p)));
        }

}

import java.util.Arrays;

public class Penazenka {

        public static boolean[] vyplatitelne(int suma, int[] platidla) {
                boolean[] vysledok = new boolean[suma + 1];
                // (ne)zabudnuty trivialny pripad !
                vysledok[0] = true;
                for (int i = 0; i < platidla.length; i++) {
                        for (int j = vysledok.length - 1; j >= 0; j--) {
                                if (!vysledok[j] && j - platidla[i] >= 0) {
                                        vysledok[j] = vysledok[j - platidla[i]];
                                }
                        }
                }
                return vysledok;
        }

        public static void main(String[] args) {
                int[] platidla = { 2, 3, 2,500,5000000,500000,500000 };
                boolean[] pomPole=Penazenka.vyplatitelne(1000000, platidla);
                System.out
                                .println(pomPole[1000000]);
        }
}

import java.io.File;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Zahradka {

        /**
         * @param args
         */

        public static void main(String[] args) {
                Scanner s = null;
                int[][] zahrada = null;
                int vyska = 0;
                int sirka = 0;
                try {
                        s = new Scanner(new File("Zahrada.txt"));
                        vyska = s.nextInt();
                        sirka = s.nextInt();
                        zahrada = new int[vyska][sirka];
                        for (int y = 0; y < vyska; y++) {
                                for (int x = 0; x < sirka; x++) {
                                        zahrada[y][x] = s.nextInt();
                                }
                        }
                } catch (Exception e) {
                        System.err.println("Zle je.");
                } finally {
                        if (s != null)
                                s.close();
                }
                int[][] pole = new int[vyska + 1][sirka + 1];
                for (int y = 1; y < vyska + 1; y++) {
                        for (int x = 1; x < sirka + 1; x++) {

                                pole[y][x] = zahrada[y - 1][x - 1]
                                                + Math.max(pole[y - 1][x], pole[y][x - 1]);
                        }
                }
                System.out.println(pole[vyska][sirka]);

                int x = sirka;
                int y = vyska;
                for (int i = 0; i < sirka + 1; i++)
                        pole[0][i] = -1;
                for (int i = 0; i < vyska + 1; i++)
                        pole[i][0] = -1;
                List<Character> cesta = new ArrayList<Character>();
                while (!(x == 1 && y == 1)) {
                        if (pole[y - 1][x] > pole[y][x - 1]) {
                                cesta.add('D');
                                y = y - 1;
                        } else {
                                cesta.add('P');
                                x = x - 1;
                        }
                }

                Collections.reverse(cesta);
                System.out.println(cesta);
        }

}