80分求助
查看原帖
80分求助
912999
13970067326a楼主2024/8/3 09:48
#include <bits/stdc++.h>

using namespace std;
int n,m;
char a[110][110];
int x[110],dp[110][1 << 11][1 << 11],ok[1 << 11],l,sum[1 << 11],ans;
int main(){
    cin >> n >> m;
    for (int i = 1; i <= n; i++){
    	for (int j = 1; j <= m; j++){
    		cin >> a[i][j];
    		if (a[i][j] == 'P'){
    			x[i]+=(1 << (m-j));
    		}
    	}
    }
    for (int i = 0; i < (1 << m); i++){
    	int f = i;
    	int s = 0;
    	while(f){
    		if (f&1){
    			s++;
    		}
    		f >>= 1;
    	}
    	sum[i] = s;
    	if ((i&(i << 2)) == 0 && (i&(i >> 2)) == 0 && (i&(i << 1)) == 0 && (i&(i >> 1)) == 0){
    		l++;
    		ok[l] = i;
         }
       }
       for (int i = 1; i <= l; i++){
       	int s1 = ok[i];
       	if ((s1|x[1]) > x[1]) continue;
       	dp[1][s1][0] = sum[s1];
       }
       for (int i = 1; i <= l; i++){
       	int s1 = ok[i];
       	if ((s1|x[2]) > x[2]) continue;
       	for (int j = 1; j <= l; j++){
       		int s2 = ok[j];
       		if ((s2|x[1]) > x[1]) continue;
       		if ((s1&s2) == 0){
       			dp[2][s1][s2] = max(dp[2][s1][s2],dp[1][s1][0]+sum[s2]);
       		}
       	  }
       }
    for (int i = 3; i <= n; i++){
    	for (int j = 1; j <= l; j++){
    		int s1 = ok[j];
    		if ((s1|x[i]) > x[i]) continue;
			for (int k = 1; k <= l; k++){
				int s2 = ok[k];
				if ((s2|x[i-1]) > x[i-1]) continue;
				for (int h = 1; h <= l; h++){
					int s3 = ok[h];
					if ((s3|x[i-2]) > x[i-2]) continue;
					if ((s1&s2) == 0 && (s2&s3) == 0 && (s1&s3) == 0){
					dp[i][s1][s2] = max(dp[i][s1][s2],dp[i-1][s2][s3]+sum[s1]);
					ans = max(ans,dp[i][s1][s2]);
					}
				}
			} 
    	}
    }
    cout << ans;
    return 0; 
} 
2024/8/3 09:48
加载中...