poj1185

状态压缩dp

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <iostream>

using namespace std;

#define MAX_COL_NUM 15

#define MAX_ROW_NUM 105

#define MAX_STAT 2050

struct Status

{

    int row_bit[];

    int last_bit_count;

}status[];

int row_num, col_num;

int grid[MAX_ROW_NUM];

int f[][MAX_STAT][MAX_STAT];

int ans;

int status_cnt;

void input()

{

    scanf("%d%d", &row_num, &col_num);

    for (int i = ; i < row_num; i++)

    {

        char row[MAX_COL_NUM];

        scanf("%s", row);

        int row_bit = ;

        for (int j = ; row[j]; j++)

        {

            if (row[j] == 'H')

            {

                row_bit = (row_bit << ) | ;

            }else

            {

                row_bit = (row_bit << ) | ;

            }

        }

        grid[i] = row_bit;

    }

}

int count_bit(int a)

{

    int ret = ;

    while (a > )

    {

        if (a & )

            ret++;

        a >>= ;

    }

    return ret;

}

bool ok(int bit)

{

    while (bit > )

    {

        if ((bit & ) == )

            return false;

        if ((bit & ) == )

            return false;

        bit >>= ;

    }

    return true;

}

bool ok(int bit, int row)

{

    return (bit & grid[row]) == ;

}

void init()

{

    memset(f, , sizeof(f));

    int col_stat = ;

    for (int i = ; i < col_num; i++)

        col_stat *= ;

    for (int i = ; i < col_stat; i++)

    {

        int temp = i;

        int row_bit[];

        row_bit[] = row_bit[] = ;

        for (int j = ; j < col_num; j++)

        {

            row_bit[] <<= ;

            row_bit[] <<= ;

            row_bit[temp % ] |= ;

            temp /= ;

        }

        if (!ok(row_bit[], ) || !ok(row_bit[], ) || !ok(row_bit[]) || !ok(row_bit[]))

        {

            f[][row_bit[]][row_bit[]] = ;

            continue;

        }

        f[][row_bit[]][row_bit[]] = count_bit(row_bit[]) + count_bit(row_bit[]);

        ans = max(ans, f[][row_bit[]][row_bit[]]);

    }

}

void make_stat()

{

    int col_stat = ;

    status_cnt = ;

    for (int i = ; i < col_num; i++)

        col_stat *= ;

    for (int i = ; i < col_stat; i++)

    {

        int temp = i;

        int row_bit[];

        row_bit[] = row_bit[] = row_bit[] = ;

        for (int j = ; j < col_num; j++)

        {

            row_bit[] <<= ;

            row_bit[] <<= ;

            row_bit[] <<= ;

            row_bit[temp % ] |= ;

            temp /= ;

        }

        bool conflict = false;

        for (int j = ; j < ; j++)

            if (!ok(row_bit[j]))

            {

                conflict = true;

                break;

            }

        if (conflict)

            continue;

        status[status_cnt].last_bit_count = count_bit(row_bit[]);

        for (int j = ; j < ; j++)

            status[status_cnt].row_bit[j] = row_bit[j];

        status_cnt++;

    }

}

void work()

{

    for (int i = ; i < row_num - ; i++)

    {

        for (int j = ; j < status_cnt; j++)

        {

            int a = status[j].row_bit[];

            int b = status[j].row_bit[];

            int c = status[j].row_bit[];

            bool conflict = false;

            for (int k = ; k < ; k++)

                if (!ok(status[j].row_bit[k], i + k))

                {

                    conflict = true;

                    break;

                }

            if (conflict)

                continue;

            f[(i + ) % ][b][c] = max(f[(i + ) % ][b][c], f[i % ][a][b] + status[j].last_bit_count);

            ans = max(ans, f[(i + ) % ][b][c]);

        }

    }

}

int main()

{

    input();

    if (row_num == )

    {

        ans = ;

        for (int i = ; i < ( << col_num); i++)

        {

            if (ok(i) && ok(i, ))

                ans = max(ans, count_bit(i));

        }

        printf("%d\n", ans);

        return ;

    }

    ans = ;

    init();

    make_stat();

    work();

    printf("%d\n", ans);

    return ;

}