AOJ2265 Programming Contest Challenge Book

問題リンク Programming Contest Challenge Book

• 解法

探索+枝刈りが方針です。
3本の棒A, B, C (A<=B<=C)が三角形になるかは
A+B < C
の三角不等式を満たすかを調べればOKです。
色々ノートで思考していると、1個目の三角形で使う棒を決めると、2個目の三角形で周辺の和が最大になるようなものは貪欲法で求められそうなことに気が付きます。未使用の棒のうち、三角形の形になるような最大の連続3本を選べばいいのです。
では1個目の三角形はどう求めるかというと、使用する最大長の棒を決めて残りを2本を色々試していきます。1個目の三角形の最大長は2個目の三角形の最大長よりも長いものとします。こうすると色々枝刈りを入れることができます。1個目の三角形の長さをai, aj, ak (ai <= aj <= ak)、暫定最適解をres、2個目の三角形の最大長をafとすると、
ai*2 <= ak
ai+aj <= ak
akから連続6本の和 <= res
ai+aj+ak+3*af <= res
のような枝刈りが入れられます。これで時間内に解けました。

• ソース

import java.util.Arrays;
import java.util.Scanner;

//Programming Contest Challenge Book
public class AOJ2265 {

	int n;
	long res;
	long[] a;
	boolean[] u;
	
	void first(int k){
		u[k] = true;
		for(int i=k-1;i>=0&&2*a[i]>a[k];i--){
			long best = 0;
			for(int j=k;j>=k-5&&j>=0;j--)best+=a[j];
			if(best<=res)break;
			u[i] = true;
			for(int j=i-1;j>=0&&a[i]+a[j]>a[k];j--){
				u[j] = true;
				int f = k-1;
				long r = -1;
				while(f>=2&&r==-1&&res < a[k]+a[i]+a[j]+3*a[f]){
					if(!u[f])r = second(f);
					f--;
				}
				if(r!=-1)res = Math.max(res, a[i]+a[j]+a[k]+r);
				u[j] = false;
			}
			u[i] = false;
		}
		u[k] = false;
	}
	
	long second(int k){
		long sum = 0;
		int c = 0;
		for(int i=k-1;i>=0&&c<2;i--)if(!u[i]){
			c++; sum+=a[i];
		}
		return c<2 || sum<=a[k]?-1:(sum+a[k]);
	}
	
	void run(){
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		a = new long[n];
		u = new boolean[n];
		res = 0;
		for(int i=0;i<n;i++)a[i]=sc.nextLong();
		Arrays.sort(a);
		for(int i=n-1;i>4;i--)first(i);
		System.out.println(res);
	}
	
	public static void main(String[] args) {
		new AOJ2265().run();
	}
}