玄学惨案现场

P2704 [NOI2001] 炮兵阵地

explorer @ 2019-11-07 13:15:49

蒟蒻求助

为什么本机上数据是正确的但是交上去有问题？... 是哪个地方习惯不好吗请各位大佬指正

#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<vector>
#include<cmath>
#define MAXN 110
#define MAXM 10
#define MAX 1<<(MAXM+1)
using namespace std;

int n,m,ground[MAXN],F[2][MAX][MAX],sit[MAX],Ans=0;
vector<int> to[MAX];
bool exsit[MAX];
inline int Count(int state){
    int res=0,x=state;
    for (; x; x-=x&(-x))    res++;
    return res;
}
inline bool Check(int state){
    for (int x=state; x; x>>=1)
        if ((((x&1)==1)+((x&2)==2)+((x&4)==4))>1)   return false;
    return true;
}
void Init(){
    memset(exsit,false,sizeof(exsit));
    memset(sit,0,sizeof(sit));
    memset(F,0,sizeof(F));
    scanf("%d%d",&n,&m);
    char op=getchar();
    for (int i=1; i<=n; i++){
        ground[i]=0;
        for (int j=0; j<m; j++){
            op=getchar();
            if (op=='P')    ground[i]=ground[i]<<1;
            if (op=='H')    ground[i]=ground[i]<<1|1;
        }
        op=getchar();
    }
}
void Pretreatment(){
    for (int state=0; state<(1<<m); state++){
        exsit[state]=Check(state);
        if (exsit[state])   sit[state]=Count(state);
    }
    for (int state=0; state<(1<<m); state++)
        for (int old=0; old<(1<<m); old++){
            if (!exsit[state] || !exsit[old] || (state&old))    continue;
            to[state].push_back(old);
        }
}
void Solve(){
    for (int state=0; state<(1<<m); state++){
        if (state&ground[1] || !exsit[state])   continue;
        for (vector<int>::iterator it=to[state].begin(); it!=to[state].end(); it++)
            F[1][state][*it]=1;
    }
    for (int i=2; i<=n; i++)
        for (int state=0; state<(1<<m); state++){
            if (!exsit[state] || state&ground[i])   continue;
            for (vector<int>::iterator it1=to[state].begin(); it1!=to[state].end(); it1++){
                int old=*it1,Max=0;F[i&1][state][old]=0;
                if (!exsit[old] || old&ground[i-1] || state&old)    continue;
                for (vector<int>::iterator it2=to[old].begin(); it2!=to[old].end(); it2++){
                    int older=*it2;
                    if (!exsit[older] || older&ground[i-2] || old&older || state&older) continue;
                    Max=max(Max,F[(i&1)^1][old][older]);
                }
                F[i&1][state][old]=Max+sit[state];
            }
        }
    for (int state=0; state<(1<<m); state++)
        for (vector<int>::iterator it=to[state].begin(); it!=to[state].end(); it++)
            Ans=max(Ans,F[n&1][state][*it]);
    printf("%d\n",Ans);
}
int main(){
    Init();
    Pretreatment();
    Solve();
    return 0;
}

附上第一个点的数据：

input:
5 4
PHPP
PPHH
PPPP
PHPP
PHHP
output:
6

但交上去就是7....

by explorer @ 2019-11-07 13:18:21

https://cdn.luogu.com.cn/upload/image_hosting/3une564t.png

by explorer @ 2019-11-07 13:18:30

@explorer 本机结果

by Smile_Cindy @ 2019-11-07 13:24:51

@explorer

现在是6了但是还是WA了

#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<vector>
#include<cmath>
#define MAXN 110
#define MAXM 10
#define MAX 1<<(MAXM+1)
using namespace std;
int getc()
{
    char ch=getchar();
    while(!isalpha(ch))ch=getchar();
    return ch;
}
int n,m,ground[MAXN],F[2][MAX][MAX],sit[MAX],Ans=0;
vector<int> to[MAX];
bool exsit[MAX];
inline int Count(int state){
    int res=0,x=state;
    for (; x; x-=x&(-x))    res++;
    return res;
}
inline bool Check(int state){
    for (int x=state; x; x>>=1)
        if ((((x&1)==1)+((x&2)==2)+((x&4)==4))>1)   return false;
    return true;
}
void Init(){
    memset(exsit,false,sizeof(exsit));
    memset(sit,0,sizeof(sit));
    memset(F,0,sizeof(F));
    scanf("%d%d",&n,&m);
    char op=getchar();
    for (int i=1; i<=n; i++){
        ground[i]=0;
        for (int j=0; j<m; j++){
            op=getc();
            if (op=='P')    ground[i]=ground[i]<<1;
            if (op=='H')    ground[i]=ground[i]<<1|1;
        }
    }
}
void Pretreatment(){
    for (int state=0; state<(1<<m); state++){
        exsit[state]=Check(state);
        if (exsit[state])   sit[state]=Count(state);
    }
    for (int state=0; state<(1<<m); state++)
        for (int old=0; old<(1<<m); old++){
            if (!exsit[state] || !exsit[old] || (state&old))    continue;
            to[state].push_back(old);
        }
}
void Solve(){
    for (int state=0; state<(1<<m); state++){
        if (state&ground[1] || !exsit[state])   continue;
        for (vector<int>::iterator it=to[state].begin(); it!=to[state].end(); it++)
            F[1][state][*it]=1;
    }
    for (int i=2; i<=n; i++)
        for (int state=0; state<(1<<m); state++){
            if (!exsit[state] || state&ground[i])   continue;
            for (vector<int>::iterator it1=to[state].begin(); it1!=to[state].end(); it1++){
                int old=*it1,Max=0;F[i&1][state][old]=0;
                if (!exsit[old] || old&ground[i-1] || state&old)    continue;
                for (vector<int>::iterator it2=to[old].begin(); it2!=to[old].end(); it2++){
                    int older=*it2;
                    if (!exsit[older] || older&ground[i-2] || old&older || state&older) continue;
                    Max=max(Max,F[(i&1)^1][old][older]);
                }
                F[i&1][state][old]=Max+sit[state];
            }
        }
    for (int state=0; state<(1<<m); state++)
        for (vector<int>::iterator it=to[state].begin(); it!=to[state].end(); it++)
            Ans=max(Ans,F[n&1][state][*it]);
    printf("%d\n",Ans);
}
int main(){
    Init();
    Pretreatment();
    Solve();
    return 0;
}

by explorer @ 2019-11-07 14:10:52

@Alpha 谢谢大佬！但是还是不是很清楚为什么直接读一个字符是错的...应该后面之后一个回车啊？

by explorer @ 2019-11-07 14:47:41

for (vector<int>::iterator it=to[state].begin(); it!=to[state].end(); it++)
            F[1][state][*it]=1;

这一句初始化错了应该改为

for (vector<int>::iterator it=to[state].begin(); it!=to[state].end(); it++)
            F[1][state][*it]=sit[state];

@Alpha