学步园

懂了这道题还不算懂插头dp。

我现在就是不懂插头dp。

要想懂插头dp就要先懂状态dp。

状态dp之于插头dp，就像 trie树之于ac自动机。

__int64 dp[13][13][1<<13];
int ok[13][13];
int n, m;


int main()
{
    int t;
    scanf("%d", &t);
    for(int tt=1; tt<=t; tt++)
    {
        scanf("%d%d", &n, &m);
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=m; j++)
                scanf("%d", &ok[i][j]);
        }

        memset(dp, 0, sizeof(dp));
        dp[0][m][0] = 1;
        for(int i=1; i<=n; i++)
        {
            for(int k=0; k<(1<<m); k++)
                dp[i][0][k<<1] = dp[i-1][m][k];
            for(int j=1; j<=m; j++)
            {
                for(int k = 0; k<( 1<<(m+1) ); k++)
                {
                    int y = 1<<j;
                    int x = 1<<(j-1);
                    if(ok[i][j])
                    {
                        if( (k&x)==0 && (k&y)==0 )
                            dp[i][j][k] = dp[i][j-1][k+x+y];
                        else if( (k&x)!=0 && (k&y)!=0 )
                            dp[i][j][k] = dp[i][j-1][k-x-y];
                        else
                            dp[i][j][k] = dp[i][j-1][k] + dp[i][j-1][k^x^y];
                    }
                    else
                    {
                        if( (k&x)==0 && (k&y)==0 )
                            dp[i][j][k] = dp[i][j-1][k];
                        else
                            dp[i][j][k] = 0;
                    }
                }
            }
        }
        printf("Case %d: There are %I64d ways to eat the trees.\n",tt, dp[n][m][0]);
    }
	return 0;
}