submarine_momodi.java

第四届百度杯预赛解题报告 武汉大学20090315

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

class M {
	int g, t, d, c;
}

public class Submarine {
	static int W, D, N, T;
	static Scanner cin = new Scanner(System.in);
	static int[][][][] dp;
	static M[] m;
	static M[][][] P;

	static void gen() {
		P = new M[T + 1][D][W];
		for (int i = 0; i < N; ++i) {
			for (int t = 0; t < W * 2 && t + m[i].t <= T; t += 2) {
				P[t + m[i].t][m[i].d][t / 2] = m[i];
				if (t + m[i].t + 1 <= T) {
					P[t + m[i].t + 1][m[i].d][t / 2] = m[i];
				}
			}
		}
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int ca = cin.nextInt();
		while (ca-- > 0) {
			W = cin.nextInt();
			D = cin.nextInt();
			N = cin.nextInt();
			T = cin.nextInt();
			m = new M[N];
			for (int i = 0; i < N; ++i) {
				m[i] = new M();
				m[i].g = cin.nextInt();
				m[i].t = cin.nextInt();
				m[i].d = cin.nextInt() - 1;
				m[i].c = cin.nextInt();
			}
			gen();
			dp = new int[T + 2][move(W * D)][W][2];
			for (int i = 0; i <= T + 1; ++i) {
				for (int j = 0; j < move(W * D); ++j) {
					for (int k = 0; k < W; ++k) {
						dp[i][j][k][0] = dp[i][j][k][1] = Integer.MIN_VALUE;
					}
				}
			}
			dp[0][0][0][0] = 0;
			for (int t = 0; t <= T; ++t) {
				for (int f = 0; f < move(W * D); ++f) {
					for (int w = 0; w < W; ++w) {
						for (int di = 0; di < 2; ++di) {
							if (dp[t][f][w][di] > Integer.MIN_VALUE) {
								int ini = dp[t][f][w][di];
								int zw = di == 0 ? 1 : -1;
								int[][] now = zz(f, t);
								int des = notFire(now, t);
								if (ini > dp[t + 1][des][w][di]) {
									dp[t + 1][des][w][di] = ini;
								}
								if (ok(w + zw) && ini > dp[t + 1][des][w + zw][di]) {
									dp[t + 1][des][w + zw][di] = ini;
								}
								int[] tmp = fire(now, t, w);
								if (ini + tmp[1] > dp[t + 1][tmp[0]][w][di ^ tmp[2]]) {
									dp[t + 1][tmp[0]][w][di ^ tmp[2]] = ini + tmp[1]; 
								}
							}
						}
					}
				}
			}
			int ans = 0;
			for (int f = 0; f < move(W * D); ++f) {
				for (int w = 0; w < W; ++w) {
					ans = Math.max(ans, dp[T + 1][f][w][0]);
					ans = Math.max(ans, dp[T + 1][f][w][1]);
				}
			}
			System.out.println(ans);
		}
	}

	static boolean ok(int k) {
		return k >= 0 && k < W;
	}

	static int[][] next(int[][] now, int t) {
		int ans[][] = new int[D][W];
		for (int i = D - 1; i >= 0; --i) {
			for (int j = W - 1; j >= 0; --j) {
				if (now[i][j] == 1) {
					if ((t - P[t][i][j].t) % 2 == 0) {
						ans[i][j] = 1;
					} else if (j + 1 < W) {
						ans[i][j + 1] = 1;
					}
				}
			}
		}
		return ans;
	}

	static int notFire(int[][] now, int t) {
		return zz(next(now, t));
	}

	static int[] fire(int[][] now, int t, int w) {
		int[] ans = new int[3];
		for (int i = 0; i < D; ++i) {
			if (now[i][w] == 1) {
				ans[1] = P[t][i][w].g;
				ans[2] = P[t][i][w].c;
				now[i][w] = 0;
				break;
			}
		}
		ans[0] = zz(next(now, t));
		return ans;
	}

	static int zz(int[][] a) {
		int ans = 0;
		for (int i = 0; i < D; ++i) {
			for (int j = 0; j < W; ++j) {
				ans = ans * 2 + a[i][j];
			}
		}
		return ans;
	}

	static int[][] zz(int k, int t) {
		int[][] ans = new int[D][W];
		for (int i = D - 1; i >= 0; --i) {
			for (int j = W - 1; j >= 0; --j) {
				ans[i][j] = k & 1;
				k >>= 1;
			}
		}
		for (int i = 0; i < N; ++i) {
			if (m[i].t == t) {
				ans[m[i].d][0] = 1;
			}
		}
		return ans;
	}

	static int move(int v) {
		return 1 << v;
	}

	static boolean take(int a, int b) {
		return ((a >> b) & 1) == 1;
	}
}