点击打开链接
思路:
经典的状态压缩题,我是来存代码的
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
typedef long long int64;
const int INF = 0x3f3f3f3f;
const int MAX_STATE = (1<<10)+10;
const int MAXN = 110;
int n, m;
int mat[MAXN], maxState;
int f[2][65][65], idx, sta[65], num[65];
inline int check(int sta){
int cnt = 0;
for(int i=0; i<m; ++i){
if( (sta>>i)&1 ){
++cnt;
for(int j=1; j<=2; ++j){
if(i-j>=0 && (sta>>(i-j))&1) return 0;
if(i+j<m && (sta>>(i+j))&1) return 0;
}
}
}
return cnt;
}
inline void init(){
maxState = (1<<m)-1;
idx = 1;
for(int i=1; i<=maxState; ++i){
int ret = check(i);
if(ret){
num[idx] = ret;
sta[idx++] = i;
}
}
}
int dp(){
memset(f, 0, sizeof(f));
int pt = 0;
int ans = 0;
for(int i=0; i<n; ++i){
pt = !pt;
for(int j=0; j<idx; ++j){
if( (mat[i]&sta[j]) != sta[j] ) continue;
if(i==0){
f[pt][j][0] = num[j];
ans = max(ans, num[j]);
}else if(i==1){
for(int k=0; k<idx; ++k){
if( (mat[i-1]&sta[k]) != sta[k]
|| (sta[j]&sta[k]) ) continue;
f[pt][j][k] = f[!pt][k][0] + num[j];
ans = max(ans, f[pt][j][k]);
}
}else {
for(int k=0; k<idx; ++k){
if( (mat[i-1]&sta[k])!=sta[k]
|| (sta[j]&sta[k]) ) continue;
int maxx = 0;
for(int l=0; l<idx; ++l) {
if( (mat[i-2]&sta[l])!=sta[l]
|| (sta[l]&sta[j])
|| (sta[l]&sta[k])) continue;
maxx = max(maxx, f[!pt][k][l]);
}
f[pt][j][k] = maxx + num[j];
ans = max(ans, f[pt][j][k]);
}
}
}
}
return ans;
}
int main(){
while(~scanf("%d%d%*c", &n, &m)){
// input
memset(mat, 0, sizeof(mat));
for(int i=0; i<n; ++i){
for(int j=0; j<m; ++j){
if(getchar()=='P'){
mat[i] |= (1<<j);
}
}
getchar();
}
init();
printf("%d\n", dp());
}
return 0;
}
分享到:
相关推荐
POJ数据略弱,此数据比POJ数据强,不过没有小数据,查错不是很方便,附AC标程
算法-炮兵阵地(POJ-1185)(包含源程序).rar
放炮问题,北大网站 POJ 1185 算法
关于poj dp分类,我一直寻找dp的分类,终于找到了,也上传一下
北大POJ3411-Paid Roads【class】 解题报告+AC代码
这是一道很不错的题目,dp解决的经典例子,是学习dp,和练习的好题目。。。。
北大POJ1184-Smart typist【搜索与状态压缩】 解题报告+AC代码
Poj 3342 这是一道树状dp题目,题意是这样的,一个公司,每个人有且仅有一个Boss,除了最大的Boss没有Boss(显然),现在要参加一个聚会,要求参加的人数最多,但是棘手的.......
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
北大POJ经典结题报告 北大POJ经典结题报告 北大POJ经典结题报告 注重方法,内容详尽,物超所值
里面有非常详细的对于POJ 2411的解题报告,相信对于初学动态规划和深度优先搜索的同学来说有很好的帮助作用。
北大poj1012-Joseph【经典约瑟夫问题】 poj1012-Joseph【经典约瑟夫问题】
北大POJ1015-Jury Compromise【动态规划DP】 解题报告+AC代码
这是黑不来就的poj上的所有dp题目的大型分类 好使好用
poj2342,树形dp,dp[i][0]表示i不参加party,其下属(包括非直接下属)能得到的最优值。dp[i][1]表示i参加的其下属和他能得到的最优值。
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
poj经典数据结构题目解题报告poj经典数据结构题目解题报告
Dp状态设计与方程总结 1.不完全状态记录 青蛙过河问题 利用区间dp 2.背包类问题 <1> 0-1背包,经典问题 无限背包,经典问题 判定性背包问题 带附属关系的背包问题 <5> + -1背包问题 双背包求最优值 构造...
帮助像我一样的oi菜鸟更好更快的理解标程,在oi界能够大显身手
C++经典代码大全,自编,很多poj上的经典题目,可供初学者参考。