HDU 5965(三行扫雷 dp)

题意是在一个 3 行 n 列的图上进行扫雷，中间一行没有雷，且中间一行的每一格都会显示周围的雷数，问根据已知的雷数在上下两行设置地雷的方法数。

分析知每一列所填雷数的和与周围的雷数有关，但每列具体的填法只影响方法数，不影响周围的雷数统计，而且每列的雷数只有 0，1，2 这三种，

用数组 dp[ ] 来记录每列的雷数，用数组 a[ ] 来记录所给的信息( 每一列出现的周围雷数的统计 )，则：

dp[ pos ] = a[ pos - 1 ] - dp[ pos - 1 ] - dp[ pos - 2 ]；

dp[ 0 ] = 0 

令 dp[ 1 ] = 0，用转移方程得到数组 dp[ ] 之后，对于每一列雷数和为 0 或 2 的情况，该列都只有一种填法，而对于每一列雷数和为 1 的情况，该列有两种填法，

用乘法原理可知：当 dp[ 1 ] = 0 时，ans =  pow(2, 单列雷数和为 1 的列数)；

同理，再求出当 dp[ 1 ] = 1 和 dp[ 1 ] = 2 的 ans，答案即为三个 ans 的和，但要注意若在求解 dp[ ] 的过程中出现所填雷数已超过规定雷数的情况或者要填多于 2 的

雷数，则该情况下的 ans不能被求和 (事实上也无法正确求出 ans )

分析样例：22

i 的值分别取 0，1，2，则 dp[ 1 ] = {0，1，2}，dp[ 2 ] 则分别填 2，1，0，

那么答案就是 sum = 1( dp[ 1 ] = 0, dp[ 2 ] = 2 ) + 4 ( dp[ 1 ] = 1, dp[ 2 ] = 1 ) + 1( dp[ 1 ] = 2, dp[ 2 ] = 0 ) = 6 

代码如下：

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e8+7;
int main()
{
    std::ios::sync_with_stdio(false);
    int t,len,pos,f,a[10005],dp[10005];
    long long ans,sum;
    string s;
    cin >>t;
    while(t--)
    {
        cin >> s;
        len = s.length();
        for(int i = 0; i < len; ++i)
            a[i+1] = s[i] - '0';
        sum = 0;
        for(int i = 0; i <= a[1] && i <= 2; ++i)
        {
            ans = 1;
            f = 1;
            dp[0] = 0;
            dp[1] = i;
            for(pos = 2; pos <= len; ++pos)
            {
                dp[pos] = a[pos-1] - dp[pos-1] - dp[pos-2];
                if(dp[pos]<0||dp[pos]>2)
                {
                    f = 0;
                    break;
                }
            }
            if(pos==len+1 && dp[len]+dp[len-1]!=a[len])
                f = 0;
            if(f)
            {
                for(int j = 1; j <= len; ++j)
                    if(dp[j]==1) ans=ans*2%mod;
                sum = (ans+sum)%mod;
            }
        }
        cout << sum << endl;
    }
    return 0;
}

感谢这些博客的作者：

与本题题解相关：

https://blog.csdn.net/elbadaernu/article/details/54773033

https://www.cnblogs.com/heimao5027/p/6033812.html

关于手动扩大栈内存（第二篇题解中涉及到这种用法，但本人的题解思路主要借鉴了第一篇题解）：

https://blog.csdn.net/shahdza/article/details/6586430

https://blog.csdn.net/f_zyj/article/details/51467501

https://www.cnblogs.com/aininot260/p/9627100.html

关于GCC优化：

https://blog.csdn.net/u010796610/article/details/69352484

https://blog.csdn.net/jiayanhui2877/article/details/11615471