PKU JudgeOnline

今日解いた問題は以下の通り，

• http://acm.pku.edu.cn/JudgeOnline/problem?id=3181
• http://acm.pku.edu.cn/JudgeOnline/problem?id=3192

他の作業をしているので今日はあんまりやっていない

以下ソース

Pku 3182

典型的なDPないしはメモ化再帰，個人的にはメモ化再帰で書く方が好き．

値がlongに入りきらないのはウサコクオリティ

import java.math.BigInteger;
import java.util.*;

public class Main {
	private static BigInteger[][] memo;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		memo = new BigInteger[n+1][k+1];
		System.out.println(f(n,k));
	}
	private static BigInteger f(int n,int k){
		if(memo[n][k]!=null)return memo[n][k];
		BigInteger res = BigInteger.ZERO;
		if(n==0){
			res = BigInteger.ONE;
		}else if(k==0){
			res = BigInteger.ZERO;
		}else{
			for(int i=0;n-i*k>=0;i++){
				res = res.add(f(n-i*k,k-1));
			}
		}
		memo[n][k] = res;
		return res;
	}
}

Pku 3192

nが7なのでnextPermutationするだけ，なお nが20ぐらいだとO(n*2^n)のアルゴリズムを検討する必要がある．

import java.util.Scanner;

public class Main {
	public static boolean nextPermutation(int[] a){
		int n = a.length;
		int i = n -2;
		for(;i>=0;i--){
			if(a[i]<a[i+1])break;
		}
		if(i<0)return false;
		//a_1,a_2...a_i < a_(i+1)>=...>=a_n
		for(int j=n-1;j>=i;j--){
			if(a[i]<a[j]){
				int tmp = a[i];
				a[i] = a[j];
				a[j] = tmp;
				break;
			}
		}
		//a_(i+1)以降をreverse
		for(int j=i+1;j<(n+i+1)/2;j++){
			int temp = a[j];
			a[j]=a[n+i-j];
			a[n+i-j]=temp;			
		}
		return true;
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int arr[] = new int[n];
		String seqs[] = new String[n];
		for(int i=0;i<n;i++){
			arr[i] = i;
			seqs[i] = sc.next();
		}
		int min = Integer.MAX_VALUE;
		do{
			String str = "";
			for(int i:arr){
				str = concat(str,seqs[i]);
			}
			min = Math.min(str.length(), min);
		}while (nextPermutation(arr));			
		System.out.println(min);
	}
	private static String concat(String a,String b){
		for(int start=0;start<a.length();start++){
			String s=a.substring(start);
			if(b.startsWith(s)){
				return a.substring(0, start).concat(b);
			}
		}
		return a.concat(b);
	}
}