首页 > 代码库 > poj 1185
poj 1185
上一题的升级版
dp[i][j][k] 表示第 i 行状态为 k 第i-1行状态为 j
#include <cstdio>#include <cstdlib>#include <cmath>#include <map>#include <set>#include <queue>#include <stack>#include <vector>#include <sstream>#include <string>#include <cstring>#include <algorithm>#include <iostream>#define maxn 2005#define INF 0x3f3f3f3f#define inf 10000000#define MOD 100000000#define ULL unsigned long long#define LL long longusing namespace std;char g[110][15];int dp[105][70][70], mapp[110], sta[70], cc[70];int n, m, num;bool if_ok(int x) { if(x & (x<<1)) return false; if(x & (x<<2)) return false; return true;}int countone(int x) { int ans = 0; while(x) { ++ ans; x = x&(x-1); } return ans;}void init() { memset(dp, -1, sizeof(dp)); memset(mapp, 0, sizeof(mapp)); num = 0; for(int i = 0; i < (1<<m); ++ i) { if(if_ok(i)) sta[num++] = i; } // printf("num : %d\n", num);}int main(){ while(scanf("%d%d", &n, &m) == 2) { init(); // printf("ff: %d\n", num); for(int i = 0; i < n; ++ i) { scanf("%s", g[i]); } for(int i = 0; i < n; ++ i) { for(int j = 0; j < m; ++ j) { if(g[i][j] == ‘H‘) mapp[i] = mapp[i] | (1<<j); } } for(int i = 0; i < num; ++ i) { cc[i] = countone(sta[i]); if((mapp[0] & sta[i]) == 0) { dp[0][0][i] = cc[i]; } } for(int i = 0; i < num; ++ i) { if(mapp[1] & sta[i]) continue; for(int j = 0; j < num; ++ j) { if(sta[j]&sta[i]) continue; if(dp[0][0][j] == -1) continue; dp[1][j][i] = max(dp[1][j][i], dp[0][0][j]+cc[i]); } } for(int i = 2; i < n; ++ i) { for(int j = 0; j < num; ++ j) { if(mapp[i] & sta[j]) continue; for(int k = 0; k < num; ++ k) { if(sta[k] & sta[j]) continue; for(int q = 0; q < num; ++ q) { if(sta[q] & sta[k] || sta[q] & sta[j]) continue; if(dp[i-1][k][q] == -1) continue; dp[i][q][j] = max(dp[i][q][j], dp[i-1][k][q]+cc[j]); } } } } int ans = 0; for(int i = 0; i < n; ++ i) { for(int j = 0; j < num; ++ j) { for(int k = 0; k < num; ++ k) { ans = max(ans, dp[i][j][k]); } } } printf("%d\n", ans); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。