哪位大佬能帮我找一下的的代码里拿错了

P2704 [NOI2001] 炮兵阵地

我不是导神 @ 2018-10-04 18:34:57

#include<cstdio>
#include<cstring>
#include<algorithm>
#define INF 1<<30

using namespace std;

int n,m;
char a[105][15];
int f[105][1<<11][1<<11],cont[1<<11],vaild[105][1<<11];
int s[1<<11];
//s[]表示相邻两个一的距离不小于三的所有位二进制集合
//cont[]表示m为二进制数x中有多少个1
//vaild[]表示x属于s,且x中的每个1对应的第i行是否都为平原
//f[i][j][k]表示第i行压缩后状态为j,第i-1行压缩后状态为k是,前i行最多放多少个炮兵 

void pretreat();

int main() {
    memset(f,-INF,sizeof(f));
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; i++) {
        char array[105];
        scanf("%s", array+1);
        for(int j = 1; j <= m; j++) {
            a[i][j] = array[j];
        }
    }
    pretreat();
    int ans;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= 1<<m; j++) {
            for(int k = 1; k <= 1<<m; k++) {
                if((j&k==0)&&vaild[i][j]&&vaild[i-1][k]) {
                    for(int l = 1; l <= 1<<m; l++) {
                        ans = 0;
                        ans = max(ans,f[i-1][k][l]);
                    }
                    f[i][j][k] = ans + cont[j];
                }
            }
        }
    }
    int sum = 0;
    for(int j = 0; j <= 1<<m; j++) {
        for(int k = 0; k <= 1<<m; k++) {
            if((j&k==0)&&vaild[n][j]&&vaild[n-1][k])  {
                sum = max(sum,f[n][j][k]);
            }
        }
    }
    printf("%d",sum);
    return 0;
}

//预处理 
void pretreat() {
    memset(s,0,sizeof(s));
    memset(vaild,0,sizeof(vaild));
    for(int i = 1; i <= 1<<m; i++) {
        for(int j = 1; j <= m; j++) {
            if(i>>j&1) {
                if(((i>>j&1)&(i>>j+1&1)) == 0 && ((i>>j&1)&(i>>j+2&1)) == 0) {
                    s[i] = 1;
                }
            }
        }
    }
    for(int i = 1; i <= 1<<m; i++) {
        if(s[i]) {
            for(int j = 1; j <= m; j++) {
                if(i>>j&1) cont[i]++;
            }
        }
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= 1<<m; j++) {
            if(s[j]) {
                for(int k = 1; k <= m; k++) {
                    if((j>>k&1)) {
                        if(a[i][k] != 'P') break;
                        else vaild[i][j] = 1;
                    }
                }
            }
        }
    }
}

by zzqDeco @ 2018-10-04 18:36:07

@冲段少年 太难了


by 我不是导神 @ 2018-10-04 19:05:26

@zzqzzqzzq 什么太难?


by zzqDeco @ 2018-10-04 19:58:40

@冲段少年 什么都难


|