为什么我是MLE

P2704 [NOI2001] 炮兵阵地

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

101×586×586×4÷1024÷1024≈132>128

还是用滚动数组吧


|