hdu1693 插头dp

题意:给了一个矩阵图，要求使用回路把图中的树全部吃掉的方案树，没有树的点不能走，吃完了这个点也就没有了，走到哪吃到哪

用插头dp搞

#include <iostream>

#include <algorithm>

#include <cstdio>

#include <vector>

#include <string.h>

using namespace std;

typedef long long LL;

int G[][];

int nrows,ncols;

struct State

{

    int up[];

    int left;

    int encode()const

    {

        int key=left;

        for(int i=; i<ncols; i++)key=key*+up[i];

        return key;

    }

    bool next(int row,int col, int U, int D, int L, int R,State &T)const

    {

        if(row==nrows- && D!= )return false;

        if(col==ncols- && R!= )return false;

        int must_left = (col>&&left!=);

        int must_up = (row> && up[col]!=);

        if( ( must_left!= && L==) || (must_left== && L!=) )return false ;

        if( ( must_up != && U== ) || (must_up == && U!= )) return false;

        for(int i=; i<ncols; i++)T.up[i]=up[i];

        T.up[col]=D;

        T.left=R;

        return true;

    }

};

LL memo[][][<<];

LL rec(int row,int col,const State &S)

{

    if(col == ncols ){ col=; row++ ;}

    if(row == nrows) return ;

    int key=S.encode();

    LL &res=memo[row][col][key];

    if(res>=)return res;

    res=;

    State T;

    if(G[row][col])

    {

       if(S.next(row,col,,,,,T))

        res+=rec(row,col+,T);

       if(S.next(row,col,,,,,T))

        res+=rec(row,col+,T);

       if(S.next(row,col,,,,,T))

        res+=rec(row,col+,T);

       if(S.next(row,col,,,,,T))

        res+=rec(row,col+,T);

       if(S.next(row,col,,,,,T))

        res+=rec(row,col+,T);

       if(S.next(row,col,,,,,T))

        res+=rec(row,col+,T);

    }else

    {

        if(S.next(row,col,,,,,T))

         res+=rec(row,col+,T);

    }

    return res;

}

int main()

{

    int cas;

    scanf("%d",&cas);

    for(int cc=; cc<=cas; cc++)

    {

        scanf("%d%d",&nrows,&ncols);

        for(int i=; i<nrows; i++)

            for(int j=; j<ncols ;j++)

            scanf("%d",&G[i][j]);

        State S;

        memset(&S,,sizeof(S));

        memset(memo,-,sizeof(memo));

        LL ans=rec(,,S);

        printf("Case %d: There are %I64d ways to eat the trees.\n",cc,ans);

    }

    return ;

}