qq825120304 @ 2018-10-20 22:48:05
为什么我优秀的代码是MLE???
认真查资料做了,测试样例自己输入也是对的,但已提交就是MLE(内存过大)
求各位dalao能看一看,指出我的错误。
#include<iostream>
#include<cstring>
using namespace std;
int dp[101][586][586];
int find(int a)
{
int t=0;
for(int i=a;i;i&=i-1)
t++;
return t;
}
int more(int a,int b)
{
return a>b ? a : b ;
}
int main()
{
//freopen("1.txt","r",stdin);
int n,sum=0,m,f[100],b[60]={0,1,2,4,8,9,16,17,18,32,33,34,36,64,65,66,68,72,73,128,129,130,132,136,137,144,145,146,256,257,258,260,264,265,272,273,274,288,289,290,292,512,513,514,516,520,521,528,529,530,544,545,546,548,576,577,578,580,584,585};
memset(dp,0,sizeof(dp));
cin>>n>>m;
int max=1<<m;
for(int i=0;i<n;i++)
{
char c;
f[i]=0;
for(int j=0;j<m;j++)
{
cin>>c;
f[i]<<=1;
if(c=='P')
f[i]++;
}
}
for(int i=0;b[i]<max;i++)
if((f[0]&b[i])==b[i])
dp[0][b[i]][0]=find(b[i]);
for(int i=0;b[i]<max;i++)
{
if((f[1]&b[i])==b[i])
for(int j=0;b[j]<max;j++)
{
if(!(b[i]&b[j]))
{
dp[1][b[i]][b[j]]=find(b[j])+find(b[i]);
}
}
}
for(int i=2;i<n;i++)
{
for(int j=0;b[j]<max;j++)
{
if((b[j]&f[i])==b[j])
for(int p=0;b[p]<max;p++)
{
if(!(b[j]&b[p])&&(b[p]&f[i-1])==b[p])
{
for(int q=0;b[q]<max;q++)
{
if(!(b[j]&b[q])&&!(b[p]&b[q])&&(b[q]&f[i-2])==b[q])
dp[i][b[j]][b[p]]=more(dp[i][b[j]][b[p]],dp[i-1][b[p]][b[q]]+find(b[j]));
}
}
}
}
}
for(int i=0;b[i]<max;i++)
{
for(int j=0;b[j]<max;j++)
{
if(dp[n-1][b[i]][b[j]]>sum)sum=dp[n-1][b[i]][b[j]];
}
}
cout<<sum;
}
by StudyForest @ 2018-11-07 22:00:30
还是用滚动数组吧