蒟蒻求助,毒瘤了好久了

P2704 [NOI2001] 炮兵阵地

一只退役蒟蒻 @ 2020-08-26 09:48:43

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdio>
#include<cmath>
#define lowbit(x) (x&-x)
#define LL long long
using namespace std;
int read()
{
    int s=0,bj=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')bj|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
    return bj?-s:s;
}
void printnum(int x)
{
    if(x>9)printnum(x/10);
    putchar(x%10^48);
}
void print(int x,char ch)
{
    if(x<0){putchar('-');x=-x;}
    printnum(x);putchar(ch);
}
int n,m,f[1<<10][1<<10][3];//no lst
int a[15],sum[71],bj[71],cnt,ans;char ch[15];
int Sum(int x)
{
    int num=0;
    while(x){x-=lowbit(x);++num;}
    return num;
}
int main()
{
    n=read();m=read();
    for(int i=1;i<=n;++i)
    {
        scanf("%s",ch);
        for(int j=0;j<m;++j)
        {
            a[i]<<=1;
            a[i]+=ch[j]=='H';
        }
    }
    for(int i=0;i<(1<<m);++i)if(!(i&(i<<1)||(i&(i<<2)))){sum[++cnt]=Sum(i);bj[cnt]=i;}
//  for(int i=1;i<=cnt;++i)if(!(bj[i]&a[1]))f[i][0][1]=sum[i];
    for(int i=1;i<=cnt;++i)
    for(int j=1;j<=cnt;++j)
    {
        if(bj[i]&bj[j]||bj[i]&a[2]||bj[j]&a[1])continue;
        f[i][j][2]=sum[i]+sum[j];//i,j,2
    }
    for(int i=3;i<=n;++i)
    for(int j=1;j<=cnt;++j)//no
    {
        if(bj[j]&a[i])continue;
        for(int k=1;k<=cnt;++k)
        {
            if((bj[k]&a[i-1])||(bj[j]&bj[k]))continue;//lst
            for(int l=1;l<=cnt;++l)//lst2
            {
                if((bj[l]&bj[k])||(bj[l]&bj[j])||(bj[l]&a[i-2]))continue;
                f[j][k][i%3]=max(f[j][k][i%3],f[k][l][(i-1)%3]+sum[j]);
            }
        }
    }
    for(int i=1;i<=cnt;++i)
    for(int j=1;j<=cnt;++j)ans=max(ans,f[i][j][n%3]);
    print(ans,'\n');
    return 0;
}

|