炮兵阵地 - POJ 1185(状态压缩)

2015-10-03 来源: 无忧望月 发布在  http://www.cnblogs.com/liuxin13/p/4853595.html

分析:先枚举出来所有的合法状态(当N=10的时候合法状态最多也就60种),用当前状态匹配上一行和上上一行的状态去匹配,看是否可以.....复杂度100*60*60*60,也可以接受。

代码如下:

=========================================================================================================================

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;

;
;

int dp[MAXN][MAXM][MAXM];

int HaveOne(int x, int N)
{
    }, sum=;

    ; i>=; i--)
    {
        s[i] = (x&);
        x >>= ;
        ] || s[i+]))
            ;
        if(s[i])sum++;
    }

    return sum;
}

int main()
{
    int M, N;

    while(scanf("%d%d", &M, &N) != EOF)
    {
        char s[MAXN];
        }, nOne[MAXM], bit[MAXM], cnt=;

        ; i<(<<N); i++)
        {
            nOne[cnt] = HaveOne(i, N);
            )
            {
                bit[cnt++] = i;
            }
        }

        ; i<=M+; i++)
        {
            scanf("%s", s);
            ; j<N; j++)
                data[i] = data[i]* + (s[j]== : );
        }

        memset(dp, false, sizeof(dp));

        ;

        ; t<=M+; t++)
        {
            ; i<cnt; i++)if( !(bit[i] & data[t]) )
            ; j<cnt; j++)]) )
            ; k<cnt; k++)]) )
            {
                if(!(bit[i] & bit[j]) && !(bit[j] & bit[k]) && !(bit[i] & bit[k]))
                {
                    dp[t][i][j] = max(dp[t][i][j], dp[t-][j][k]+nOne[i]);
                    ans = max(ans, dp[t][i][j]);
                }
            }
        }

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

    ;
}

相关文章