http://hihocoder.com/contest/offers52/problems
题目2 : 亮灯方案
BFS+memo，重复的数组还是蛮多的

package l522;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt(), m=sc.nextInt();
        char[][]a=new char[n][m];
        int sum=0;
        for(int i=0;i<n;i++) {
            a[i]=sc.next().toCharArray();
            for(int j=0;j<m;j++) {
                if(a[i][j]=='0') sum++;
            }
        }
        
        int[][] dirs={{-1,0},{1,0},{0,1},{0,-1}};
        Map<String, Long> map = new HashMap<String, Long>();
        System.out.println(dfs(a,n,m,dirs,sum,map));
    }

    private static long dfs(char[][] a, int n, int m, int[][] dirs, int sum, Map<String, Long> map) {
        if(sum==0) return 0;
        if(sum==1) return 1;
        StringBuilder sb = new StringBuilder();
        for(char[] tt:a) sb.append(new String(tt));
        if(map.containsKey(sb.toString())) return map.get(sb.toString());
        
        long res = 0;
        Set<String> s = new HashSet<String>();
        for(int i=0; i<n; i++)
            for(int j=0;j<m;j++) {
                if(a[i][j]=='1') {
                    for(int[] d: dirs) {
                        int ii=i+d[0],jj=j+d[1];
                        if(ii>=0&&ii<n && jj>=0&&jj<m && a[ii][jj]=='0' && !s.contains((ii+"_"+jj))) {
                            s.add(ii+"_"+jj);
                            a[ii][jj] = '1';
                            res += dfs(a, n, m, dirs,sum-1,map);
                            a[ii][jj] = '0';
                        }
                    }
                }
            }
        
        map.put(sb.toString(), res);
        return res;
    }
}

题目3 : 部门聚会
没有下级的人肯定会参加，所以先考虑这些人，然后把这些人抹去，剩下来的人可以参加，也可以不参加，
继续选择那些没有下级的人，分别计算他们参加与不参加的情况下，这个人所属下级最多能喝酒的单位，如此循环
其实就是BFS顺序下的DP，写的时候感觉都把入度和出度都计算出来吧。
然后还有个trick就是不用map来保存每个人对应的上级，就用数组，index为0定义为原始root的上级

package l523;

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        int[]a=new int[n+1];
        for(int i=1;i<=n;i++)a[i]=sc.nextInt();
//        Map<Integer, Integer> up = new HashMap<Integer, Integer>();
        // up use array, default to zero
        int[] up = new int[1+n];
        Map<Integer, Set<Integer>> dn = new HashMap<Integer, Set<Integer>>();
        int[] children = new int[1+n];
        for(int i=0; i<=n; i++) {
            dn.put(i, new HashSet<Integer>());
        }
        for(int i=0; i<n-1; i++) {
            int u=sc.nextInt(), v=sc.nextInt();
            dn.get(u).add(v);
            up[v]=u;
//          up.put(v,u);
            children[u]++;
        }
        int root=1;
        for(root=1; root<=n;root++) if(up[root]==0) break;
        dn.get(0).add(root);
        children[0] = 1;
        
        Queue<Integer> q = new LinkedList<Integer>();
        Queue<Integer> qq = new LinkedList<Integer>();
        for(int i=1;i<=n;i++) if(dn.get(i).size()==0) q.add(i);
        
        double[] in = new double[1+n], out = new double[1+n];
        while(q.size()!=0) {
            while(q.size()!=0) {
                int t=q.remove();
                int u = up[t];
                children[u]--;
                if(children[u]==0) {
                    qq.add(u);
                    
                    double not_come = 0;
                    for(int c : dn.get(u))
                        not_come += Math.max(in[c]+a[c], out[c]);
                    out[u] = not_come;
                
                    double come = 0;
                    for(int c : dn.get(u))
                        come += Math.max(in[c]+a[c]*0.5, out[c]);
                    in[u] = come;
                }
            }
            
            q=qq;
            qq=new LinkedList<Integer>();
        }
        
        System.out.printf("%.1f", Math.max(in[0], out[0]));
    }
}