首页 > 代码库 > hdu 1185 状压dp 好题 （当前状态与上两行有关系）
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 好题 （当前状态与上两行有关系）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。