hdu 1185 状压dp 好题（当前状态与上两行有关系）

/*

状压dp

刚开始&写成&&看了好长时间T0T.

状态转移方程

 dp[i][k][j]=Max(dp[i][k][j],dp[i-1][l][k]+num[i][j]);(第i行的第j个状态有上一行的第k个状态得到)

 num[i][j]有两个功能，第一：判断第i行第j个状态是否合法

                      第二：判断第i行第j个状态的数目

*/

#include<stdio.h>

#include<string.h>

#define N 110

int dp[N][N][N];

char s[N][N];

int len;

int ss[N],ans,num[N][N];

int n,m;

int lower[20];

int f(int i,int d)

{

    int k=0,j;

    for(j=0; j<m; j++)

    {

        if(lower[j]&d&&s[i][j+1]=='H')return -1;

        if(lower[j]&d&&s[i][j+1]=='P')k++;

    }

    return k;

}

int Max(int v,int vv)

{

    return v>vv?v:vv;

}

void slove()

{

    int i,j,k,l;

    memset(dp,-1,sizeof(dp));

    len=0;

    for(i=0; i<(1<<m); i++)

    {

        if(((i<<1)&i)||((i<<2)&i))continue;

        ss[len++]=i;

    }

    memset(num,-1,sizeof(num));

    for(i=1; i<=n; i++)

        for(j=0; j<len; j++)

        {

            k=f(i,ss[j]);

            if(k!=-1)

                num[i][j]=k;

            //printf("%d %d %d\n",i,j,num[i][j]);

        }

    for(i=0; i<len; i++)//初始化第一行

    {

        num[0][i]=0;

        if(num[1][i]==-1)continue;

        dp[1][0][i]=num[1][i];//因为0的是否没有下面ss[j]&ss[l]的限制

        if(ans<dp[1][0][i])

            ans=dp[1][0][i];

    }

    for(i=2; i<=n; i++)

        for(j=0; j<len; j++)

        {

            if(num[i][j]==-1)continue;

            for(k=0; k<len; k++)

            {

                if(num[i-1][k]==-1)continue;

                for(l=0; l<len; l++)

                {

                    if(num[i-2][l]==-1)continue;

                    if(ss[j]&ss[k])continue;

                    if(ss[j]&ss[l])continue;

                    if(dp[i-1][l][k]==-1)continue;

                    dp[i][k][j]=Max(dp[i][k][j],dp[i-1][l][k]+num[i][j]);

                 //   printf("%d %d %d %d %d %d\n",i,num[i][j],dp[i][k][j],dp[i-1][l][k],ss[j],ss[k]);

                    if(ans<dp[i][k][j])

                        ans=dp[i][k][j];

                }

            }

        }

    return ;

}

int main()

{

    int i;

    lower[0]=1;

    for(i=1; i<=12; i++)

        lower[i]=lower[i-1]*2;

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        for(i=1; i<=n; i++)

            scanf("%s",s[i]+1);

        ans=-1;

        slove();

        printf("%d\n",ans);

    }

    return 0;

}

巴特西

hdu 1185 状压dp 好题（当前状态与上两行有关系）

最新文章

热门文章

巴特西

hdu 1185 状压dp 好题 （当前状态与上两行有关系）

最新文章

热门文章

hdu 1185 状压dp 好题（当前状态与上两行有关系）