POJ1664 메모리 귀환, 간단하고 알기 쉽다

1066 단어 私人
import java.io.File; import java.io.FileNotFoundException; import java.util.Scanner;
public class DivideApple3 {
static long[][] results;

public static void main(String[] args) throws FileNotFoundException {
    // TODO Auto-generated method stub
    results=new long[10001][11];
    @SuppressWarnings("resource")
    Scanner sc = new Scanner(System.in);
    sc = new Scanner(new File("files/apple"));
    int T = sc.nextInt();
    for (int t = 0; t < T; t++) {
        int m = sc.nextInt();
        int n = sc.nextInt();
        System.out.println(DFS(m, n));
    }
}

private static long DFS(int m, int n) {
    // TODO Auto-generated method stub
    if (m == 0 || n == 1)
        return 1;
    if(results[m][n]!=0)
        return results[m][n];
    for (int i = 0; i <= m / n; i++) {
        results[m][n] += DFS(m - i * n, n - 1);
    }
    return results[m][n];
}

}
sample input: 6 7 3 10 5 2 1 30 2 1000 10 10000 10
sample output: 8 30 1 16 968356321790171 3016757406431865393

좋은 웹페이지 즐겨찾기