SRM 389 Level2 1000
http://www.topcoder.com/stat?c=problem_statement&pm=8545&rd=11123
吉他有若干根弦，和弦有若干个音，按某弦的某节可以改变其音
求某和弦的最简单按发（各个弦按节最接近）

由于上限是6，数据比较小，
每个弦上需要考虑的点不超过12个
所以全部遍历也只有12^6种情况
又是递归，简单的深搜
  1import java.util.*;
  2import java.util.regex.*;
  3import java.text.*;
  4import java.math.*;
  5import java.awt.geom.*;
  6
  7public class GuitarChords
  8{
  9    //arrays
 10    String[] notes = {"A", "A#", "B", "C", "C#", "D", "D#", "E", "F", "F#", "G", "G#"};
 11    int best = Integer.MAX_VALUE;
 12    int[][] table;
 13    int[] dest;
 14    int[]  open;
 15    int[] ans;
 16    int L,N;
 17    
 18    public int stretch(String[] strings, String[] chord)
 19    {
 20        //length of the string and the chords
 21        L = strings.length;
 22        N = chord.length;
 23        
 24        //table
 25        table = new int[L][24];
 26        dest = new int[N];
 27        ans = new int[L];
 28        open = new int[L];
 29        for(int[] t : table)
 30            Arrays.fill(t, -1);
 31        
 32        //data parse
 33        //positive numbers for chord notes, -1 for else
 34        int i , j;
 35        for(i = 0 ; i < N ; ++ i){
 36            for(j = 0 ; j < 12 ; ++ j)
 37                if(chord[i].compareTo(notes[j]) == 0)
 38                    dest[i] = j;
 39        }
 40        for( i = 0 ; i < L;  ++ i){
 41            for(j = 0 ; j < 12; ++ j){
 42                if(strings[i].compareTo(notes[j]) == 0)
 43                    open[i] = j;
 44                
 45            }
 46            for(int k = 0; k < N; ++ k){
 47                int temp = dest[k] - open[i];
 48                if(temp < 0)
 49                    temp += 12;
 50                table[i][temp] = dest[k];
 51                table[i][temp+12] = dest[k];
 52            }
 53        }
 54//        for(int[] t:table){
 55//            for(int in:t)
 56//                System.out.print(in+" ");
 57//            System.out.println();
 58//        }
 59            
 60        //search
 61        solve(0);
 62        return best;
 63    }
 64    
 65    void solve(int idx){
 66        loop:
 67        for(int i = 0 ; i < 24; ++ i){
 68            
 69            //get next valid note
 70            if(table[idx][i] == -1)
 71                continue;
 72            ans[idx] = i;
 73            
 74            //come to the last string
 75            if(idx == L-1){
 76                
 77                //check whether every note appears
 78                boolean[] app = new boolean[N];
 79                Arrays.fill(app, false);
 80                for(int j = 0 ; j < L; ++ j){
 81                    for(int k = 0 ; k < N; ++ k){
 82                        if(table[j][ans[j]] == dest[k])
 83                            app[k] = true;
 84                    }
 85                }
 86                for(boolean b:app)
 87                    if(b == false)
 88                        continue loop;
 89                
 90                //get the lowest and the highest
 91                int[] temp = ans.clone();
 92                Arrays.sort(temp);
 93                if(temp[L-1] == 0)
 94                    best = 0;
 95                int j;
 96                for(j = 0 ; j < L-1; ++ j){
 97                    if(temp[j]!=0)
 98                        break;
 99                }
100                int diff = temp[L-1] - temp[j] + 1;
101                
102                //update the answer
103                if(diff<best) 
104                    best = diff;
105                continue ;
106            }
107            
108            //search next position
109            solve(idx+1);
110        }
111    }
112}