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
几乎没有位运算,也叫状压吗
我是噶黑!!!