Untitled

mail@pastecode.io avatar
unknown
plain_text
17 days ago
1.5 kB
1
Indexable
Never
import java.util.Scanner;

public class Solution {
	static int n, B[], max, sum, visit[];

	public static void main(String[] args)  {
		// TODO Auto-generated method stub

		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();

		for (int tc = 1; tc <= T; tc++) {
			n = sc.nextInt();
			B = new int[n];
			for (int i = 0; i < n; i++) {
				B[i] = sc.nextInt();
			}

			visit = new int[n];

			sum = 0;
			max = 0;
			shot(0);
			System.out.println("Case #" + tc);
			System.out.println(max);
		}
		sc.close();
	}

	private static void shot(int k) {
		// TODO Auto-generated method stub
		if (k == n) {
			max = sum > max ? sum : max;
			return;
		}

		for (int i = 0; i < n; i++) {
			if (visit[i] == 0) {
				visit[i] = 1;

				int tmp = sum;

				int l = getLeft(i);
				int r = getRight(i);

				if (l >= 0 && r >= 0) {
					sum += B[i - l] * B[r + i];
				}
				if (l < 0 && 0 <= r && r < n) {
					sum += B[r + i];
				} else if (r < 0 && l >= 0 && l < n) {
					sum += B[i - l];
				} else if (r < 0 && l < 0) {
					sum += B[i];
				}

				shot(k + 1);

				sum = tmp;
				visit[i] = 0;
			}
		}

	}

	private static int getRight(int s) {
		// TODO Auto-generated method stub
		for (int i = s; i < n; i++) {
			if (visit[i] == 0)
				return i - s;
		}
		return -1;
	}

	private static int getLeft(int s) {
		// TODO Auto-generated method stub
		for (int i = s; i >= 0; i--) {
			if (visit[i] == 0)
				return s - i;
		}

		return -1;
	}

}
Leave a Comment