AOJ0246 Bara-Bara Manju

問題リンク Bara-Bara Manju

• 解法

深さ優先探索+枝刈りが方針です。
何をどう深さ優先探索したのかという話になりますが、ずばり、「10の作り方」です。
10を和で表現する方法は調べてみると41通りあります。この10の作り方それぞれに番号を振り、k番の10の作り方を使って10を作る個数を探索します。枝刈りのために、残っている整数の総和をSとします。すると、どんなに頑張っても残りS/10個しかおまんじゅうを詰めれません。これを使って解が更新できるかをチェックします。
まだ時間が足りません。そこで、(1, 9)(2, 8)(3, 7)(4, 6)(5, 5)というまんじゅうの詰め方を作れるだけ作っておきます。これらはまんじゅうを2個だけ使う事で10を作れます。まんじゅうは使える整数が減れば減るほど10を作りづらくなるので、これらは貪欲に作ってよいのです。

• ソース

import java.util.Scanner;

//Bara-Bara Manju
public class AOJ0246 {
	
	int res, num, ID;
	int[][] div;
	int[] c, u;
	
	void f(int k, int rest){
		if(rest==0){
			for(int i=1;i<10;i++)div[ID][i] = u[i];
			ID++;
			return;
		}
		if(k<=0)return;
		for(int use=0;use*k<=rest;use++){
			u[k] = use;
			f(k-1, rest-use*k);
			u[k] = 0;
		}
	}
	
	void dfs(int k, int num, int sum){
		res = Math.max(res, num);
		if(k==ID || num+sum/10 <= res)return;
		int t = 1000;
		for(int i=1;i<10;i++)if(div[k][i]>0)t = Math.min(t, c[i]/div[k][i]);
		for(int use=0;use<=t;use++){
			for(int i=1;i<10;i++)c[i]-=use*div[k][i];
			dfs(k+1, num+use, sum-use*10);
			for(int i=1;i<10;i++)c[i]+=use*div[k][i];
		}
	}
	
	void run(){
		Scanner sc = new Scanner(System.in);
		div = new int[50][11];
		u = new int[11];
		f(9, 10);
		for(;;){
			int n = sc.nextInt();
			if(n==0)break;
			c = new int[11];
			int sum = 0;
			for(int i=0;i<n;i++){
				int x = sc.nextInt();
				c[x]++;
				sum+=x;
			}
			int g = c[5]/2;
			sum-=g*10;
			c[5]%=2;
			for(int i=6;i<10;i++){
				int t = Math.min(c[i], c[10-i]);
				sum-=10*t;
				g+=t;
				c[i]-=t;
				c[10-i]-=t;
			}
			res = 0;
			dfs(0, g, sum);
			System.out.println(res);
		}
	}
	
	public static void main(String[] args) {
		new AOJ0246().run();
	}
}