Programozás‎ > ‎Feladatok‎ > ‎Szabályos háromszögek‎ > ‎Megoldás‎ > ‎

szabalyos.java

Letöltés: szabalyos.java

import java.util.Scanner;
import java.io.*;

class Megoldo{
    int DB,S;
    int[] a;
    int[][] cacheA, cacheB;
    int INF = 10000000;
   
    public Megoldo(int db, int[] adat, int sum){
            DB = db;
            a = adat;
            S = sum;
            cacheA = new int[S+1][S+1];
            cacheB = new int[S+1][S+1];
    }
       
    public int solve(){
        // i = 1
        for(int d1 = 0; d1<= S; d1++){
            for(int d2 = d1; d2<=S; d2++)
            {
                cacheA[d1][d2] = -INF; // ha nem jöhet ki ilyen
                if(d1 == a[0] && d2 == a[0]) cacheA[d1][d2] = d1;
            }
        }
       
       
        // i = 2..DB
        for(int i=1; i < DB; i++){
           
            for(int d1 = 0; d1<=S; d1++)
            for(int d2 = d1; d2<=S; d2++)
            {
                // 1. eset: nem használjuk az új pálcikát                
                cacheB[d1][d2] = cacheA[d1][d2];                
               
                // 2. eset: az új pálcika egyedül               
                if(a[i]==d1 && d2==d1 && d1 > cacheB[d1][d2]){
                    cacheB[d1][d2] = d1;               
                }
               
                // 3. eset: a legmagasabb toronyra raktuk               
                if(    d1 >= a[i] &&
                    a[i]+cacheA[d1-a[i]][d2-a[i]] > cacheB[d1][d2]){
                        cacheB[d1][d2] = a[i]+cacheA[d1-a[i]][d2-a[i]];                   
                }
               
                // 4A. eset: a középső toronyra raktuk és átfordul               
                if(    d1<=a[i] && a[i]-d1 <= d2-d1 &&
                    d1+cacheA[a[i]-d1][d2-d1] > cacheB[d1][d2]){
                        cacheB[d1][d2] = d1+cacheA[a[i]-d1][d2-d1];                       
                }
               
                // 4B. eset: a középső toronyra raktuk és nem fordul át               
                if(    d1+a[i]<=d2 &&
                    cacheA[d1+a[i]][d2] > cacheB[d1][d2]){
                        cacheB[d1][d2] = cacheA[d1+a[i]][d2];               
                }
                               
                // 5a. eset: a legkisebbre raktuk és nem fordul át               
                if(    d2+a[i] <= S &&
                    cacheA[d1][d2+a[i]] > cacheB[d1][d2]){
                        cacheB[d1][d2] = cacheA[d1][d2+a[i]];                           
                }
               
                // 5b. eset: a legkisebbre raktuk és középre kerül                
                if(    d1+a[i] >= d2 && d1+a[i] <= S &&
                    cacheA[d2][d1+a[i]] > cacheB[d1][d2]){
                        cacheB[d1][d2] = cacheA[d2][d1+a[i]];                   
                }
               
                // 5c. eset: a legkisebbre raktuk és a legnagyobb lett               
                if(    a[i]>= d2 &&
                    cacheA[d2-d1][a[i]-d1]+d1 > cacheB[d1][d2]){
                        cacheB[d1][d2] = cacheA[d2-d1][a[i]-d1]+d1;                   
                }                               
            }           
            int[][] tmp = cacheA;cacheA = cacheB;cacheB = tmp;
        }
        return cacheA[0][0]>0?cacheA[0][0]:0;
    }
}

class szabalyos{
       
    public static void main(String args[]) throws FileNotFoundException{
        Scanner be = new Scanner(new FileReader("10.in"));
        int DB = be.nextInt();
        while(DB > 0){ //tesztesetek
            int[] a = new int[DB];
            int S = 0;
            for(int i=0; i < DB; i++){
                a[i] = be.nextInt();
                S += a[i];
            }
            Megoldo M = new Megoldo(DB, a, S);
           
            System.out.println(M.solve());
            DB = be.nextInt();
        }
    }
}