代码如下
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include<iostream>
#include<cmath>
#include<vector>
#include<map>
#define INF 0x3f3f3f3f
#define MAXN 200010
typedef long long ll;
using namespace std;
int a[110],dp[3][1<<10][1<<10],sum[1<<10];
int n,m;
void getsum()
{
    for(int i=0; i<(1<<m); i++)
    {
        int res=0,x=i;
        while(x)
        {
            if(x&1)
                res++;
            x>>=1;
        }
        sum[i]=res;
    }
}
inline bool judge(int x)
{
    if((x&(x<<1))||(x&(x<<2)))
        return true;
    return false;
}
int main()
{
    cin>>n>>m;
    getsum();
    char ch;
    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
        {
            cin>>ch;
            a[i]<<=1;
            a[i]+=(ch=='H'?1:0);
        }
    for(int i=0; i<(1<<m); i++)
        if(!(judge(i)||(i&a[0])))
            dp[0][0][i]=sum[i];
    for(int i=0; i<(1<<m); i++)
        for(int j=0; j<(1<<m); j++)
            if(!(judge(i)||(i&a[0])||judge(j)||(j&a[1])||(i&j)))
                dp[1][i][j]=sum[i]+sum[j];
    for(int i=2; i<n; i++)
    {
        for(int p2=0; p2<(1<<m); p2++)
        {
            if(judge(p2)||(p2&a[i-2]))
                continue;
            for(int p1=0; p1<(1<<m); p1++)
            {
                if(judge(p1)||(p1&a[i-1])||(p1&p2))
                    continue;
                for(int cur=0; cur<(1<<m); cur++)
                {
                    if(judge(cur)||(cur&a[i])||(cur&p1)||(cur&p2))
                        continue;
                    dp[i%3][p1][cur]=max(dp[i%3][p1][cur],dp[(i-1)%3][p2][p1]+sum[cur]);
                }
            }
        }
    }
    int ans=0;
    for(int i=0; i<(1<<m); i++)
    {
        if(judge(i)||(i&a[n-2]))continue;
        for(int j=0; j<(1<<m); j++)
        {
            if(judge(j)||(j&a[n-1])||(i&j))continue;
            ans=max(ans,dp[(n-1)%3][i][j]);
        }
    }
    cout<<ans<<endl;
}

• Re:为什么一份代码用c++交超时,g++1300多ms,g++难道优化了什么吗 (2176) megadeth_ 2019-08-19 16:45:58
• 好像知道了,g++把"i++"优化成"++i"了 (0) megadeth_ 2019-08-19 16:47:20