ICPC2005 ProblemF

動的計画法

import java.util.*;

public class Gathm {
       static class Person {
                int id;
                List<Integer> freeDays;
                List<Integer> pieaces;
                public Person(int id) {
                        this.id = id;
                        this.freeDays = new ArrayList<Integer>();
                        pieaces = new ArrayList<Integer>();
                        pieaces.add(id);
                }

                void addFreeDay(Integer day) {
                        freeDays.add(day);
                }

                public boolean haveAllPieaces(int max) {
                        boolean res = true;
                        for(int i = 0; i < max; i++) {
                                if(!this.pieaces.contains(i)) {
                                        res = false;
                                }
                        }
                        return res;
                }
        }

        public static void main(String[] argc)
        {
                Scanner scn = new Scanner(System.in);
                while(true) {
                        int n = scn.nextInt();
                        if(n == 0) break;
                        Person[] people = new Person[n];
                        //read data
                        for(int i = 0; i < n; i++) {
                                people[i] = new Person(i);
                                int f0 = scn.nextInt();
                                for(int j = 0; j < f0; j++) {
                                        people[i].addFreeDay(scn.nextInt());
                                }
                        }
                        int i;
                        for(i = 1; i <=  30; i++) {
                                List<Person> freePerson = new ArrayList<Person>();
                                List<Integer> pieaces = new ArrayList<Integer>();
                                //For all person
                                for(int j = 0; j < n; j++) {
                                        if(people[j].freeDays.contains(i)) {
                                                freePerson.add(people[j]);
                                                for(int k = 0; k < people[j].pieaces.size(); k++) {
                                                        if(!pieaces.contains(people[j].pieaces.get(k))) {
                                                                pieaces.add(people[j].pieaces.get(k));
                                                        }
                                                }
                                        }
                                }
                                for(int j = 0; j < freePerson.size(); j++) {
                                        freePerson.get(j).pieaces = pieaces;
                                }
                                boolean finishp = false;
                                for(int j = 0; j < n; j++) {
                                        if(people[j].haveAllPieaces(n)) {
                                                finishp = true;
                                                break;
                                        }
                                }
                                if(finishp) {
                                        break;
                                }
                        }
                        if(i == 31) {
                                System.out.println("-1");
                        }
                        else {
                                System.out.println(i);
                        }
                }
        }
}