cf-208B - Solitaire-記錄狀態DFS

比賽的時候竟然沒想起來記錄狀態，好搓啊。。。

int dp[n][i][j][k];長度為n，第n-2個的狀態為i，第n-1個的狀態為j，第n個的狀態為k，能不能成功操作。

這樣時間復雜度為(52*52*52*52）；

#include
#include
#include
#include
#include
#include
#define INF 1000000
using namespace std;
char va[15]={'2','3','4','5','6','7','8','9','T','J','Q','K','A'};
char su[5]={'S','D','H','C'};
int dp[60][60][60][60];
int a[60];
int pan(int x,int y)
{
    if(x%4==y%4)return 1;
    if(x/4==y/4)return 1;
    return 0;
}
int dfs(int ns,int x,int y,int z)
{
    if(dp[ns][x][y][z]!=-1)return dp[ns][x][y][z];
    if(ns<=3)
    {
        if(pan(x,z)&&pan(y,z))
        {
            dp[ns][x][y][z]=1;
        }
        else dp[ns][x][y][z]=0;
        return dp[ns][x][y][z];
    }
    int leap=0;
    if(pan(y,z)&&      dfs(ns-1,a[ns-3],x,z))leap=1;
    if(pan(a[ns-3],z)&&dfs(ns-1,z      ,x,y))leap=1;
    dp[ns][x][y][z]=leap;
    return leap;
}
int main()
{
    int n,m,i,j,k;
    char str[11];
    while(~scanf("%d",&n))
    {
        memset(dp,-1,sizeof(dp));
        for(i=1;i<=n;i++)
        {
            scanf("%s",str);
            for(j=0;j<13;j++)
                if(str[0]==va[j])a[i]=j;
            for(j=0;j<4;j++)
                if(str[1]==su[j])a[i]=a[i]*4+j;
        }
        if(n<3)
        {
            if(n==1)cout<<"YES"<