求助大佬 调了好久了 都快抄题解了…还没看出哪里错

P2704 [NOI2001] 炮兵阵地

zhutier @ 2018-08-27 16:16:47

来自一只超级弱的我

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int n,m,dp[102][1005][1005],obs[103],sit[103],t,answer,g[103];
char a;
int num(int x){
    int r=x,ans=0;
    while(r>0){
        if(r&1) ans++;
        r=r>>1;
    }
    return ans;//   printf("the number is%d,it has %d one\n",x,ans);
}
bool jud(int x){
    if(x&(x<<1)) return true;
    if(x&(x<<2)) return true;
    else return false;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a;
            if(a=='H') obs[i]+=(1<<(m-j));
        }
    //  printf("obs[%d]=%d\n",i,obs[i]);
    }
    for(int i=0;i<(1<<m);i++){
        if(!jud(i)){
            t++;
            sit[t]=i;
            g[t]=num(i);
            if((i&obs[1])==0) dp[1][0][t]=g[t];//printf("dp[1][0][%d]=%d\n",t,dp[1][0][t]);
        }
    }
    for(int i=1;i<=t;i++)
        if((sit[i]&obs[1])==0){
            for(int j=1;j<=t;j++){
                if((sit[j]&obs[2])==0&&(sit[j]&sit[i])==0)
                    dp[2][i][j]=max(dp[2][i][j],dp[1][0][i]+g[j]);//printf("dp[2][][]=%d\n",dp[2][i][j]);
            }
        }
    for(int i=3;i<=n;i++)
        for(int j=1;j<=t;j++)//i
            if((sit[j]&obs[i])==0){
                for(int k=1;k<=t;k++)//i-1
                    if((sit[k]&obs[i-1])==0&&(sit[k]&sit[j])==0){
                        for(int q=1;q<=t;q++){//i-2
                            if((sit[q]&obs[i-2])==0&&(sit[q]&sit[k])==0){
                                dp[i][k][j]=max(dp[i][k][j],dp[i-1][q][k]+g[j]);
                            }
                        }
                    }
            }
    for(int i=1;i<=t;i++)
        for(int j=1;j<=t;j++){
            answer=max(answer,dp[n][i][j]);
        //  printf("dp=%d\n",dp[n][i][j]);
        }
    printf("%d\n",answer);
    return 0;
}

by 闻染 @ 2018-08-27 16:23:17

那就吸氧吧,实在不行就抄题解


by zhutier @ 2018-08-27 16:25:36

@sushitong (滑稽)


by goodlearndaydayup @ 2018-08-27 16:27:30

代码过长,不予回复


by zhutier @ 2018-08-27 16:29:04

@违规用户名XRSq*3EK

哭唧唧 其实就三块 初始化第一行 初始化第二行 算接下来的 真的不长的真的不长的


by zhutier @ 2018-08-27 16:39:14

我终于

在抄题解的过程中

找到了bug

给这题过不去的大兄弟一个忠告

三行记得

互相&都要等于0

脑子有点晕忘了

debug四小时


by zhutier @ 2018-08-27 16:40:17

好的 我MLE了 继续解决问题


by _216612 @ 2018-10-19 15:39:33

呵呵

|