经典的状态压缩DP。
dp[i][j][k] = max( dp,dp[i-1][k][k2] );
k是前一行的状态,k2是前二行的状态。
/*
dp[i][j][k] = max( dp,dp[i-1][k][k2] );
k是前一行的状态,k2是前二行的状态。
*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<iostream>
#include<queue>
#include<stack>
#include<math.h>
#include<map>
using namespace std;
const int maxn = 105;
const int maxm = 12;
const int N = 65;
int mat[ maxn ],mm[ maxn ][ maxm ];
int dp[ maxn ][ N ][ N ];
int state[ maxn ],ones_state[ maxn ];
int GetSum( int x ){
int sum = 0;
while( x ){
if( x&1 )
sum++;
x>>=1;
}
return sum;
}
int init_state( int n,int m ){
int M = (1<<m);
int cnt =0;
memset( state,0,sizeof( state ) );
memset( ones_state,0,sizeof( ones_state ) );
for( int i=0;i<M;i++ ){
if( (i&(i<<1))==0&&(i&(i<<2))==0&&(i&(i>>1))==0&&(i&(i>>2))==0 ){
state[ cnt ] = i;
ones_state[ cnt++ ] = GetSum( i );
}
}
//printf("cnt=%d\n",cnt);
return cnt;
}
void DP( int cnt,int n,int m ){
memset( dp,-1,sizeof( dp ) );
for( int i=0;i<cnt;i++ ){
if(( mat[0]&state[i] )==0)
dp[ 0 ][ i ][ 0 ] = ones_state[ i ];
}
for( int i=1;i<n;i++ ){
for( int j=0;j<cnt;j++ ){
if( (mat[i]&state[j])==0 ){
for( int k=0;k<cnt;k++ ){
if( (state[j]&state[k])==0 ){
for( int k2=0;k2<cnt;k2++ ){
if( dp[i-1][k][k2]==-1 ) continue;
if( (state[j]&state[k2])==0&&(state[k]&state[k2])==0 ){
dp[i][j][k] = max( dp[i][j][k],dp[i-1][k][k2]+ones_state[j] );
}
}
}
}
}
}
}
return ;
}
int main(){
int n,m;
while( scanf("%d%d",&n,&m)==2 ){
int cnt = init_state( n,m );
char s[ maxm ];
for( int i=0;i<n;i++ ){
scanf("%s",s);
for( int j=0;j<m;j++ ){
if( s[j]=='P' )
mm[i][j] = 1;
else
mm[i][j] = 0;
}
}
memset( mat,0,sizeof( mat ) );
for( int i=0;i<n;i++ ){
for( int j=0;j<m;j++ ){
if( mm[i][j]==0 )
mat[i] |= (1<<j);
}
}
DP( cnt,n,m );
int ans = 0;
for( int i=0;i<cnt;i++ ){
for( int j=0;j<cnt;j++ ){
ans = max( ans,dp[n-1][i][j] );
}
}
printf("%d\n",ans);
}
return 0;
}
分享到:
相关推荐
poj 800+ 题目源代码,多年做题积累 包含各种类型经典题目
放炮问题,北大网站 POJ 1185 算法
北大POJ3411-Paid Roads【class】 解题报告+AC代码
POJ数据略弱,此数据比POJ数据强,不过没有小数据,查错不是很方便,附AC标程
关于poj dp分类,我一直寻找dp的分类,终于找到了,也上传一下
poj1085,记忆化DP+状态压缩求解
北大POJ1184-Smart typist【搜索与状态压缩】 解题报告+AC代码
Poj 3342 这是一道树状dp题目,题意是这样的,一个公司,每个人有且仅有一个Boss,除了最大的Boss没有Boss(显然),现在要参加一个聚会,要求参加的人数最多,但是棘手的.......
2505 2521 2538 2546 2551 2590 2593 2601 2665 2680 2739 2752 2761 2762 2777 2800 2891 2893 2992 3030 3041 3132 3159 3187 3204 3270 3277 3281 3297 3321 3414 3436 3461 3650 3663 3664 3672 3740
这是一道很不错的题目,dp解决的经典例子,是学习dp,和练习的好题目。。。。
这是黑不来就的poj上的所有dp题目的大型分类 好使好用
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
北大POJ1015-Jury Compromise【动态规划DP】 解题报告+AC代码
北大POJ初级-简单搜索 解题报告+AC代码
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
poj2342,树形dp,dp[i][0]表示i不参加party,其下属(包括非直接下属)能得到的最优值。dp[i][1]表示i参加的其下属和他能得到的最优值。
帮助像我一样的oi菜鸟更好更快的理解标程,在oi界能够大显身手
北大POJ1159-Palindrome 解题报告+AC代码
西北工业大学POJ试题C++答案代码+课程设计
北大POJ2002-Squares 解题报告+AC代码