大佬们,复习好了吗?!

P2704 [NOI2001] 炮兵阵地

ghruik @ 2019-11-15 10:07:06

大佬们复习好了,可以帮我这个小蒟蒻,改一下状压dp吗

#include<bits/stdc++.h>
using namespace std;
int u[13],m,n,o;
char a[101][100];
int f[110][70][70],ans,b[10000];
int et(int x)
{
    int ci=1;
    memset(u,0,sizeof(u));
    while (x>0)
    {
        if (x%2==1) {
                        u[ci]=1;
                    }
        x/=2;ci++;
    }
    for (int i=1;i<=m;i++)
        {
            if (i-2>0&&u[i]==1&&u[i-2]==1) return 0;
            if (i-1>0&&u[i]==1&&u[i-1]==1) return 0;
            if (i+1<=m&&u[i]==1&&u[i+1]==1) return 0;
            if (i+2<=m&&u[i]==1&&u[i+2]==1) return 0;
        }
    return 1;
}
int ffi(int a1,int a2,int a3)
{
    if (a1&a2!=0) return 0;
    if (a2&a3!=0) return 0;
    if (a1&a3!=0) return 0;
    return 1;
}
int ge(int f)
{   int yu=0;
    while (f>0)
    {
        if (f%2==1) yu++;
        f/=2;
    }
    return yu;
}
int find(int ci,int k)
{
    if (ci<=0) return 1;
    int oo=1;
    while (k>0)
    {
        if (k%2==1&&a[ci][oo]=='p') return 0;
        k/=2;
        oo++;
    }
    return 1;
}
int main()
{
    scanf("%d%d",&n,&m);
    getchar();
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=m;j++)
                a[i][j]=getchar();
                getchar();
    }
    for (int i=0;i<=(1<<m);i++)
        if (et(i))  
            {
                o++;
                b[o]=i;
            }
    for (int i=1;i<=n;i++)
        {
            for (int l=1;l<=o;l++)
                for (int j=1;j<=o;j++)
                    for (int k=1;k<=o;k++)
                    {
                        if (find(i-1,b[j])==0||find(i-2,b[k])==0||find(i,b[l])==0) continue;
                        if (ffi(b[j],b[l],b[k]))    f[i][l][j]=max(f[i][l][j],f[i-1][j][k]+ge(b[l]));
                    }

        }
    for (int l=1;l<=o;l++)
        for (int j=1;j<=o;j++)
            ans=max(ans,f[n][l][j]);
    printf("%d",ans);
}

本人并没有用滚动数组,而是选择离散化,然而,或许是我对状压理解不够吧。样例都过不掉。求大佬帮助


by Mosklia @ 2019-11-15 10:23:57

@ghruik 讲个恐怖故事:这个题不需要过掉样例也能拿 70 pts


by Binah @ 2019-11-15 10:27:05

find不需要这么写啊,直接和1<<a做与操作就可以判了


by ghruik @ 2019-11-15 10:28:12

@Sparky_14145 我改了改,过掉样例了然后我T飞了


by Binah @ 2019-11-15 10:28:21

x在2进制第a位为1和x与1<<a为真是等价的 (从第0位开始记录)


by ghruik @ 2019-11-15 10:28:43

@Flowey 那样写着并不是很舒服没就没有那样写


by Agakiss @ 2019-11-15 10:31:16

几乎没有位运算,也叫状压吗

我是噶黑!!!


|