Aizu Online Judge 0070 Combination of Number Sequences

■0070 Combination of Number Sequences

探索?
TLE
高速化したよー
TLE

～長い年月～

やっぱDPじゃん
テキトーに組む
TLE
ま・さ・か
実は探索?
nとsの範囲が実は狭いことに気付く(n≦10，s≦330)．大きい場合は絶対に存在しない．
ばっち枝刈りしたZE
TLE
あるぇー（・３・）
nとsが小さいんだから，予めDPで生成しておけるよねー．
前に書いたDPを流用
AC

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.  static final int INF=1<<28;  
14.  static final double EPS=1e-9;  
15.   
16.  int n, s;  
17.  int[][] sum;  
18.   
19.  void run(){  
20.   n=10;  
21.   s=330;  
22.   init();  
23.   for(; sc.hasNext();){  
24.    n=sc.nextInt();  
25.    s=sc.nextInt();  
26.    if(n<=10&&s<=330){  
27.     println(sum[n-1][s]+"");  
28.    }else{  
29.     println("0");  
30.    }  
31.   }  
32.   sc.close();  
33.  }  
34.   
35.  void init(){  
36.   int[][] dp=new int[s+1][1<<10];  
37.   int[][] dp2=new int[s+1][1<<10];  
38.   sum=new int[n][s+1];  
39.   dp[0][0]=1;  
40.   
41.   for(int j=0; j<n; j++){  
42.    for(int i=0; i<=s; i++){  
43.     System.arraycopy(dp[i], 0, dp2[i], 0, 1<<10);  
44.     Arrays.fill(dp[i], 0);  
45.    }  
46.    for(int i=0; i<10; i++){  
47.     int d=(j+1)*i;  
48.     for(int b=0; b<1<<10; b++){  
49.      if(((1<<i)&b)==0){  
50.       for(int k=0; k+d<=s; k++){  
51.        dp[k+d][(1<<i)|b]+=dp2[k][b];  
52.       }  
53.      }  
54.     }  
55.    }  
56.    for(int i=0; i<=s; i++){  
57.     for(int b=0; b<1<<10; b++){  
58.      sum[j][i]+=dp[i][b];  
59.     }  
60.    }  
61.   }  
62.  }  
63.   
64.  void debug(Object... os){  
65.   System.err.println(Arrays.deepToString(os));  
66.  }  
67.   
68.  void print(String s){  
69.   System.out.print(s);  
70.  }  
71.   
72.  void println(String s){  
73.   System.out.println(s);  
74.  }  
75.   
76.  public static void main(String[] args){  
77.   new Main().run();  
78.  }  
79. }  

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);

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

 int n, s;
 int[][] sum;

 void run(){
  n=10;
  s=330;
  init();
  for(; sc.hasNext();){
   n=sc.nextInt();
   s=sc.nextInt();
   if(n<=10&&s<=330){
    println(sum[n-1][s]+"");
   }else{
    println("0");
   }
  }
  sc.close();
 }

 void init(){
  int[][] dp=new int[s+1][1<<10];
  int[][] dp2=new int[s+1][1<<10];
  sum=new int[n][s+1];
  dp[0][0]=1;

  for(int j=0; j<n; j++){
   for(int i=0; i<=s; i++){
    System.arraycopy(dp[i], 0, dp2[i], 0, 1<<10);
    Arrays.fill(dp[i], 0);
   }
   for(int i=0; i<10; i++){
    int d=(j+1)*i;
    for(int b=0; b<1<<10; b++){
     if(((1<<i)&b)==0){
      for(int k=0; k+d<=s; k++){
       dp[k+d][(1<<i)|b]+=dp2[k][b];
      }
     }
    }
   }
   for(int i=0; i<=s; i++){
    for(int b=0; b<1<<10; b++){
     sum[j][i]+=dp[i][b];
    }
   }
  }
 }

 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){
  new Main().run();
 }
}