Problem
http://acm.sjtu.edu.cn/OnlineJudge/problem/1229 Mine
Description
扫雷是一个很经典的小游戏，而一行数字一行雷的题目就更经典了。当然，这道题不能这么简单就算了。
问题是这样，有一个两行n列的格子，第一行里不会有雷，第二行里不会有数字。给定第一行的某些数字，数字代表该格子正下方与左右两个斜下方共三个格子里雷数目的总和。问下一行最多有多少个雷，并给出一个让雷尽可能靠后的方案（最后一个雷尽可能靠后，如果相同，倒数第二个雷尽可能靠后，以此类推）。保证一定存在一种合法的地雷安放方案。
Input Format
第一行一个整数n，表示格子的列数
第二行为一个长度为n的字符串，由‘0’、‘1’、‘2’、‘3’以及‘’组成。表示第一行的数字，‘’表示该格数字未定，保证不含其他字符（行末回车符除外）
Output Format
第一行为一个整数，表示最多的地雷数目
第二行为一个长度为n的字符串，由‘0’和‘1’组成，‘0’代表安全，‘1’代表有地雷。表示所要求的安放方案
Sample Input
2 1*Sample Output
1 01数据规模
10%数据 ：1<=n<=10 40%数据 ：1<=n<=100000，输入中不出现‘*’号 100%数据：1<=n<=100000
Analysis
dp一遍过。。。
用f[i][pre][now]表示前i位串，倒数第二位状态是pre，本位状态是now的最多地雷数。
f[i][pre][now] =
max{
f[i-1][0][pre]+now (if 0+pre+now == a[i-1] or a[i-1]=='*'),
f[i-1][1][pre]+now (if 1+pre+now == a[i-1] or a[i-1]=='*')
}
初始
f[1][0][0]=0
f[1][0][1]=1
最后检验所有满足pre+now == a[n]的f[n][pre][now]，取最大的一组。
注意，由于满足最右端最大，转移方程中应优先选择第二种情况，最后时候应优先选择01而不是10。
为了记录状态，开一个b[i][pre][now]，表示在[i][pre][now]的情况下，f取得最大值时，i-2位应该取什么，这样在最后就能反向遍历了。