10pts 只过了sub0的1#和sub1求助

P2704 [NOI2001] 炮兵阵地

AzukaVictor @ 2022-03-11 22:00:45

#include<bits/stdc++.h>
using namespace std;
int n,m,st[1<<10],mp[1<<10],dp[101][1<<10][1<<10],num[1<<10],ans;
char c[20];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>c;
        for(int j=0;j<m;j++)
        {
            if(c[j]=='H')
            {
                mp[i]+=1;
            }
            mp[i]<<=1;
        }
        mp[i]>>=1;
    }

    for(int i=0;i<(1<<m);i++)
    {
        int sum=0;
        for(int j=i;j>0;j>>=1)
        {
            if((j&1)==1) sum++;
        }
        num[i]=sum;
        if(!(i&(i<<2))&&!(i&(i>>2))&&!(i&(i<<1))&&!(i&(i>>1)))
        {
            if((mp[1]&i)==0)
            dp[1][i][0]=num[i];
            st[i]=1;
        }
    }
    for(int i=0;i<(1<<m);i++)
    {
        for(int j=0;j<(1<<m);j++)
        {
            if((st[i]&st[j])==1&&(mp[2]&i)==0&&(mp[1]&j)==0&&(i&j)==0)
            {
                dp[2][i][j]=max(dp[2][i][j],dp[1][j][0]+num[i]);
             } 
        }
    }
    for(int i=3;i<=n;i++)
    {
        for(int j=0;j<(1<<m);j++)
        {
            if(st[j]==1&&(mp[i]&j)==0)
            for(int k=0;k<(1<<m);k++)
            {
                if(st[k]==1&&(j&k)==0&&(k&st[i-1])==0)
                for(int f=0;f<(1<<m);f++)
                {
                    if((k&f)==0&&(j&f)==0&&(f&st[i-2])==0&&st[f]==1)
                    {
                        dp[i][j][k]=max(dp[i][j][k],dp[i-1][k][f]+num[j]);
                    }
                }

            } 
        } 
    }
    for(int i=0;i<(1<<m);i++)
    {
        for(int j=0;j<(1<<m);j++)
        {
            ans=max(ans,dp[n][i][j]);
        }
    }
    cout<<ans<<endl;
    return 0;
}

rt,调了半天没出来,也不是优先级问题,求大佬指点


by ZkjTCTC @ 2022-03-25 23:14:57

dp[101][1<<10][1<<10],同志是dp[101][1<<11][1<<11]吧。数据看清楚


by ZkjTCTC @ 2022-03-25 23:18:02

st,num同理。状态也有1111111111啊


by heleans @ 2022-09-17 10:51:32

@ZkjTCTC 1111111111不也在1<<10范围内吗


|