玄学问题,开启O2会出错
查看原帖
玄学问题,开启O2会出错
1301844
trailfight楼主2024/10/11 19:28
#include<bits/stdc++.h>
using namespace std;
const int N=105, M=60;
int n, m, a[N], status[N][M], len[N], cnt[M], dp[N][M][M], ans;
char ch[M];
void dfs(int h, int s, int l, int num){
	cnt[s]=num;
	if(l>=m) return;
	if(a[h]&(1<<l)){
		status[h][++len[h]]=s|1<<l;
		dfs(h, s|1<<l, l+3, num+1);
	}
	dfs(h, s, l+1, num);
}
int main(){
	scanf("%d%d", &n, &m);
	for(int i=0; i<n; ++i){
		scanf("%s", &ch);
		for(int j=0; j<m; ++j){
			if(ch[j]=='P') a[i]=a[i]|1<<j;
		}
	}
	for(int i=0; i<n; ++i){
		dfs(i, 0, 0, 0);
	}
	for(int i=0; i<=len[0]; ++i){
		dp[0][i][0]=cnt[status[0][i]];
		ans=max(ans, dp[0][i][0]);
	}
	for(int i=1; i<n; ++i){
		for(int j=0; j<=len[i]; ++j){
			for(int k=0; k<=len[i-1]; ++k){
				if(status[i][j]&status[i-1][k]) continue;
				if(i<2){
					dp[i][j][k]=max(dp[i][j][k], dp[i-1][k][0]+cnt[status[i][j]]);
					ans=max(ans, dp[i][j][k]);
				}else{
					for(int l=0; l<=len[i-2]; ++l){
						if(status[i][j]&status[i-2][l] || status[i-1][k]&status[i-2][l]) continue;
						dp[i][j][k]=max(dp[i][j][k], dp[i-1][k][l]+cnt[status[i][j]]);
						ans=max(ans, dp[i][j][k]);
					}
				}
			}
		}	
	}
	printf("%d\n", ans);
    return 0;
}

2024/10/11 19:28
加载中...