Linyong GAN

题意

雷区有两行，只有第一行有埋雷。现在给定第二行体现出来的周围雷的个数，求方案数。

思路

显然（结合标签也可以看出来）是一道动态规划。动规难的就是状态的构建和转移，真正的代码实现并不复杂。

动规方程构建

记 dp[i][j] 表示在 i 位置的状态为 j，前 i 个位置有的方案数。其中 j 为状态的代号，对应表如下：{0: .., 1: .*, 2: *., 3: **}。其中 * 为雷， . 为非雷。

方程初始

dp[0][c] = 1 if c is valid w.r.t A[0] for any c
dp[0][c] = 0 if c is not valid w.r.t A[0] for any c

方程转移

dp[i][c1] += dp[i-1][c2] for any c1, c2 and they are valid w.r.t A, i, c1, c2

代码

import java.util.Scanner;

public class P1024Minesweeper
{
	public static int check_valid_first(int[] A, int i, int c)
	{
		if(A[i] == 0 && c == 0) return 1;
		if(A[i] == 1 && (c == 1 || c == 2)) return 1;
		if(A[i] == 2 && c == 3) return 1;
		return 0;
	}
	public static int check_valid(int[] A, int i, int c1, int c2)
	{
		if(A[i] == 0 && (c1 == 0 && c2 == 0)) return 1;
		if(A[i] == 1 && ((c1 == 1 && c2 == 2) || (c1 == 0 && c2 == 1) || (c1 == 2 && c2 == 0))) return 1;
		if(A[i] == 2 && ((c1 == 3 && c2 == 2) || (c1 == 2 && c2 == 1) || (c1 == 1 && c2 == 3))) return 1;
		if(A[i] == 3 && (c1 == 3 && c2 == 3)) return 1;
		return 0;
	}
	public static void main(String[] args)
	{
		Scanner sc = new Scanner(System.in);
		int n = Integer.parseInt(sc.nextLine());
		String[] Astr = sc.nextLine().split(" ");
		int[] A = new int[n];
		for(int i = 0; i < n; i++)
			A[i] = Integer.parseInt(Astr[i]);

		int[][] dp = new int[n][4];
		for(int i = 0; i < 4; i++) dp[0][i] = check_valid_first(A, 0, i);
		
		for(int i = 1; i < n; i++)
			for(int c1 = 0; c1 < 4; c1++)
				for(int c2 = 0; c2 < 4; c2++)
					dp[i][c1] += dp[i-1][c2] * check_valid(A, i, c1, c2);

		System.out.println(dp[n-1][0]+dp[n-1][1]+dp[n-1][2]+dp[n-1][3]);
	}
}

反思

如何设计动规方程？显然会带一个位置信息，一维已经去了，最多还能来一维，而且不能是给位置相关的（不然就开不下了）。
两种可能性：一是这题真就够了，直接用一个位置转移全；二是还必须要带一个要素，但不能占空间太大。
显然这题不可能一个位置转移到底，因为这还跟雷的分布有很大的关系。
很难的一点是如何把A的值和雷的分布去映射起来，而且dp中存的还应该是方案数。单纯的数学好像是不能解决了，所以用函数去判断是不是合法的，或者说是把雷的状态和A对应起来。
这样看，第二维只需要记录雷的状态就可以了。先考虑只记录当前位置的状态。如果当前位置是雷，但不知道前后的情况，依然不能判断是不是合法，所以重新考虑把前后带进来。因此是记录当前和下一个，一共四种状态。
这样状态方程就设计出来了。
至于结论在什么位置，一般是取全部的总和、取全部的最大值或者取最后的状态。方案数想要转移，结果应该就是存在最后一个位置的。