记录编号	195039	评测结果	AAAAAAAAAA
题目名称	[NOI 2001]炮兵阵地	最终得分	100
用户昵称	啊吧啦吧啦吧	是否通过	通过
代码语言	C++	运行时间	0.155 s
提交时间	2015-10-17 20:55:12	内存使用	1.94 MiB

#include <cstdio>
#include <iostream>
#include <cstdlib>
 
using namespace std;
 
int n, m, maxl, b[111][61], sh[111], s[111][61], f[111][61][61];
bool p[111][11];
char c;
void dfs(int, int, int, int);
 
main()
{
	freopen("cannon.in", "r", stdin);
	freopen("cannon.out", "w", stdout);
    cin >> n >> m;
     
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j){
            cin >> c;
            if (c == 'P')
                p[i][j]=1;
        }
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            if(p[i][j])
                dfs(i, j, 1, 1 << (j - 1));
    for(int i = 0; i <= sh[1]; ++i)
        for(int j = 0; j <= sh[2]; ++j)
            if(! (b[1][i] & b[2][j]))
                f[2][j][i] = s[1][i] + s[2][j];
    for (int i = 3; i <= n; ++i)
        for (int j = 0; j <= sh[i]; ++j)
            for (int k = 0;k <= sh[i - 1]; ++k)
                if (! (b[i][j] & b[i - 1][k]))
                    for (int q = 0; q <= sh[i - 2]; ++q)
                        if (!(b[i][j]&b[i-2][q])&&!(b[i-1][k]&b[i-2][q])&&f[i][j][k]<f[i-1][k][q]+s[i][j]){
                            f[i][j][k] = f[i - 1][k][q] + s[i][j];
                            maxl = max(maxl, f[i][j][k]);
                    }
     
    cout << maxl;
}
 
void dfs(int x, int y, int sum, int stat)
{
    b[x][++sh[x]] = stat;
    s[x][sh[x]] = sum;
    for (y += 3; y <= m; ++y)
    if (p[x][y])
    dfs(x, y, sum + 1, stat | (1 << (y - 1)));
}