首页 > 代码库 > 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;}