Aizu Online Judge

■1204 Pipeline Scheduling

再帰を用いて実際にシミュレートする．左端から詰めていくようにして，簡単な枝刈り（現時点でのサイクル数が，暫定の最短より長い場合は中断）を付け加えれば通る．

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5.   
6. import static java.lang.Math.*;  
7. import static java.util.Arrays.*;  
8.   
9. public class Main{  
10.   
11.  Scanner sc=new Scanner(System.in);  
12.   
13.  int INF=1<<28;  
14.  double EPS=1e-9;  
15.   
16.  int n, t, u;  
17.  int[][] a, b;  
18.  int ans;  
19.   
20.  void run(){  
21.   t=10;  
22.   u=5;  
23.   for(;;){  
24.    n=sc.nextInt();  
25.    if(n==0){  
26.     break;  
27.    }  
28.    a=new int[u][n];  
29.    for(int j=0; j<u; j++){  
30.     String s=sc.next();  
31.     for(int i=0; i<n; i++){  
32.      a[j][i]=s.charAt(i)=='.'?0:1;  
33.     }  
34.    }  
35.    solve();  
36.   }  
37.  }  
38.   
39.  void rec(int k, int p){  
40.   if(p>=ans){  
41.    return;  
42.   }  
43.   if(k==t+1){  
44.    ans=min(ans, p+n-1);  
45.    return;  
46.   }  
47.   for(int q=p; q<p+n; q++){  
48.    boolean f=true;  
49.    for(int j=0; j<u; j++){  
50.     for(int i=0; i<n; i++){  
51.      f&=a[j][i]==0||b[j][q+i]==0;  
52.     }  
53.    }  
54.    if(f){  
55.     for(int j=0; j<u; j++){  
56.      for(int i=0; i<n; i++){  
57.       if(a[j][i]==1){  
58.        b[j][q+i]=k;  
59.       }  
60.      }  
61.     }  
62.     rec(k+1, q+1);  
63.     for(int j=0; j<u; j++){  
64.      for(int i=0; i<n; i++){  
65.       if(a[j][i]==1){  
66.        b[j][q+i]=0;  
67.       }  
68.      }  
69.     }  
70.    }  
71.   }  
72.  }  
73.   
74.  void solve(){  
75.   ans=INF;  
76.   b=new int[u][(n+1)*(t+1)];  
77.   rec(1, 0);  
78.   println(""+ans);  
79.  }  
80.   
81.  void debug(Object... os){  
82.   System.err.println(Arrays.deepToString(os));  
83.  }  
84.   
85.  void print(String s){  
86.   System.out.print(s);  
87.  }  
88.   
89.  void println(String s){  
90.   System.out.println(s);  
91.  }  
92.   
93.  public static void main(String[] args){  
94.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
95.   new Main().run();  
96.  }  
97. }  

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int n, t, u;
 int[][] a, b;
 int ans;

 void run(){
  t=10;
  u=5;
  for(;;){
   n=sc.nextInt();
   if(n==0){
    break;
   }
   a=new int[u][n];
   for(int j=0; j<u; j++){
    String s=sc.next();
    for(int i=0; i<n; i++){
     a[j][i]=s.charAt(i)=='.'?0:1;
    }
   }
   solve();
  }
 }

 void rec(int k, int p){
  if(p>=ans){
   return;
  }
  if(k==t+1){
   ans=min(ans, p+n-1);
   return;
  }
  for(int q=p; q<p+n; q++){
   boolean f=true;
   for(int j=0; j<u; j++){
    for(int i=0; i<n; i++){
     f&=a[j][i]==0||b[j][q+i]==0;
    }
   }
   if(f){
    for(int j=0; j<u; j++){
     for(int i=0; i<n; i++){
      if(a[j][i]==1){
       b[j][q+i]=k;
      }
     }
    }
    rec(k+1, q+1);
    for(int j=0; j<u; j++){
     for(int i=0; i<n; i++){
      if(a[j][i]==1){
       b[j][q+i]=0;
      }
     }
    }
   }
  }
 }

 void solve(){
  ans=INF;
  b=new int[u][(n+1)*(t+1)];
  rec(1, 0);
  println(""+ans);
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}