晴空一鹤 @ 2021-03-14 19:07:03
调了 1 h
结果调得T越来越多,WA越来越少(尽管仍然是0分)
#include<bits/stdc++.h>
using namespace std;
int s[101][171][171],cnt=0,ans=0;
int l[171];
int n,m;
char aaa[101][101],ccc;
void inline csh(int x)
{
for(int i=0;i<1<<x;i++)
if(((i&(i>>1))==0)&&((i&(i>>2))==0)&&(((i>>1)&(i>>2))==0))
l[++cnt]=i;
}
int inline cha(int y,int u)
{
int x=0;
while(y&(-y))
{
if(aaa[u][(int)log(y&(-y))+1]=='P')x++;
y-=y&(-y);
}
return x;
}
void inline dp()
{
for(int i=1;i<=n;i++)
for(int j=1;j<=cnt;j++)
for(int x=1;x<=cnt;x++)
for(int ll=1;ll<=cnt;ll++)
{
int v=cha(l[j],i);
if((l[ll]&l[j]&l[x])==0)
s[i][l[j]][l[x]]=max(s[i][l[j]][l[x]],s[i-1][l[x]][l[ll]]+v);
ans=max(ans,s[i][l[j]][l[x]]);
}
}
int main()
{
cin>>n>>m;ccc=getchar();
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
cin>>aaa[i][j];
ccc=getchar();
}
csh(m);
dp();
cout<<ans<<endl;
}
(话说这为啥会T)
给if(l[ll]&l[j]&l[x]==0) 加上括号后T会变多
这不科学
by zimujun @ 2021-03-14 19:10:11
@晴空一鹤 首先,dp 数组开小了,既然
by 晴空一鹤 @ 2021-03-14 19:11:37
但是老师说cnt最多只会有70
by 晴空一鹤 @ 2021-03-14 19:12:25
@zimujunqwq
by zimujun @ 2021-03-14 19:14:42
好吧我可能神必了,我再看看,对不起
by zimujun @ 2021-03-14 19:15:46
i<1<<x
位运算优先级低于逻辑运算,加上括号
by 晴空一鹤 @ 2021-03-14 19:16:44
o 好的 我去试试
by zimujun @ 2021-03-14 19:19:35
@晴空一鹤 不用试,数组开小了,必然不对
by 晴空一鹤 @ 2021-03-14 19:19:47
@zimujunqwq
好像还是6WA4TLE
我再看看吧
by 晴空一鹤 @ 2021-03-14 19:20:54
开始后悔我为什么删除刚才说的话
by 晴空一鹤 @ 2021-03-14 19:22:13
由于很多状态是无效的,所以cnt不会上百