学步园

看了看某PPT后，乱写了一下午~~

下面的代码写法上不是最优的，但能体现思路，合写了的话就会根本不知道怎么来的：

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

const int N=12;
const int NN=1<<N;

int n,m,b,s[N][N];
long long dp[N][N][NN];

bool One(int x,int p)
{
    if (x&(1<<p)) return true;
    else          return false;
}

bool Zero(int x,int p)
{
    if (x&(1<<p)) return false;
    else          return true;
}

int main()
{
    int cases,casecnt=0;
    scanf("%d",&cases);
    while (cases--)
    {
        //input & init
        scanf("%d%d",&n,&m);
        for (int i=1; i<=n; i++)
            for (int j=1; j<=m; j++) scanf("%d",&s[i][j]);
        memset(dp,0,sizeof(dp));
        for (int j=0; j<=m; j++) dp[0][j][0]=1;
        b=(1<<(m+1))-1;
        
        //DP
        for (int i=1; i<=n; i++)
        {
            for (int k=0; k<=b>>1; k++)
                dp[i][0][k<<1] = dp[i-1][m][k];
                
            for (int j=1; j<=m; j++)
            {
                for (int k=0; k<=b; k++)
                {
                    if (s[i][j]==0) // (i,j)位置上没有树
                    {
                        if (Zero(k,j-1) && Zero(k,j))
                            dp[i][j][k] += dp[i][j-1][k];
                        continue;
                    }
                    if (Zero(k,j-1) && Zero(k,j))
                    {
                        dp[i][j][k^(3<<(j-1))] += dp[i][j-1][k]; // 六种路径方向，3:30(时钟位置)
                    }
                    if (Zero(k,j-1) && One(k,j))
                    {
                        dp[i][j][k] += dp[i][j-1][k]; // 3:00
                        dp[i][j][k^(3<<(j-1))] += dp[i][j-1][k]; // 6:00
                    }
                    if (One(k,j-1) && Zero(k,j))
                    {
                        dp[i][j][k] +=dp[i][j-1][k];   // 6:45
                        dp[i][j][k^(3<<(j-1))] += dp[i][j-1][k]; // 9:15
                    }
                    if (One(k,j-1) && One(k,j))
                    {
                        dp[i][j][k^(3<<(j-1))] += dp[i][j-1][k]; // 9:00
                    }
                }
            }
        }
        if (n==1 || m==1) dp[n][m][0]=0;
        printf("Case %d: There are %I64d ways to eat the trees.\n",++casecnt,dp[n][m][0]);
    }
    return 0;
}

这个DP思想重点（对于这题）在于考虑在整体之下的个体的根本规律，我们通过每格的应有姿态(回路中的点一进一出两个插头)来推算整体，又想到这种表达不难却很难想到的DP路径和状态，好厉害的说。继续学习。