gobang.java

第四届百度杯编程大赛final解题报告+标程

import java.io.*;
import java.util.*;

public class gobang {
	static int a[][];
	static int b[][];
	static int st_exp[];
	static int n;
	
	static int point[];
	static int exp[];
	
	static int dp() {
		point = new int[1 << n];
		exp = new int[1 << n];
		Arrays.fill(point, 0);
		Arrays.fill(exp, -1);
		point[0] = 0;
		exp[0] = st_exp[0];
		int ret = 0;
		
		for (int i = 0; i < (1 << n); i++) if ((i & 1) == 0) {
			for (int j = 1; j < n; j++) {
				if (((i >> j) & 1) == 0) {
					exp[i | (1 << j)] = exp[i] + a[0][j];
				}
			}
		}
		
		for (int i = 0; i < (1 << n); i++) {
			if ((i & 1) == 0) {
				for (int j = 1; j < n; j++) {
					if (((i >> j) & 1) == 0 && exp[i] > st_exp[j]) {
						int new_point = point[i] + b[0][j];
						int new_i = i | (1 << j);
						if (new_point > point[new_i]) {
							point[new_i] = new_point;
							if (new_point > ret)
								ret = new_point;
						}
					}
				}
			}
		}
		return ret;
	}
	
	public static void main(String args[]) throws Exception {
		Scanner cin = new Scanner(System.in);
		int ca = cin.nextInt();
		for (int c = 0; c < ca; c++) {
			n = cin.nextInt();
			a = new int[n][n];
			b = new int[n][n];
			st_exp = new int[n];
			for (int i = 0; i < n; i++)
				for (int j = 0; j < n; j++)
					a[i][j] = cin.nextInt();
			for (int i = 0; i < n; i++)
				for (int j = 0; j < n; j++)
					b[i][j] = cin.nextInt();
			for (int i = 0; i < n; i++)
				st_exp[i] = cin.nextInt();
			int ans = dp();
			System.out.println(ans);
		}
	}
}