滚动数组求调试,谢谢
查看原帖
滚动数组求调试,谢谢
255762
lyxleo楼主2022/10/27 14:27

这个代码没过样例,我挑不出来,故求大佬调试,谢谢

#include <iostream>
#include <string.h>
using namespace std;
unsigned int n,m;
unsigned int state[105];//表示每一行的空地 
unsigned int dp[3][1 << 11][1 << 11];
unsigned int ones[1 << 11];
inline bool check(const int &i){
	return ((i & (i << 1)) == 0 && (i & (i << 2)) == 0);
}
int main(){
	cin>>n>>m;
	for(unsigned int i = 0;i < (1 << m);++i){
		unsigned int s = 0;
		for(unsigned int j = i;j;j -= (j & (-j))) ++s;
		ones[i] = s;
	}
	for(unsigned int i = 0;i < n;++i){
		for(unsigned int j = 0;j < m;++j){
			char c;
			cin>>c;
			if(c == 'P'){
				state[i] += (1 << j);
			}
		}
	}
	
	for(unsigned int j = 0;j < (1 << m);++j){
		if((j & state[0]) == j && check(j)){
			for(unsigned int k = 0;k < (1 << m);++k){
				dp[0][j][k] = ones[j];
			}
		}
	}
	if(n == 1){
		unsigned int ans = 0;
		for(unsigned int j = 0;j < (1 << m);++j){
			if((j & state[0]) == j && check(j)){
				for(unsigned int k = 0;k < (1 << m);++k){
					ans = max(ans,dp[0][j][k]);
				}
			}
		}
		cout<<ans;
		return 0;
	}
	for(unsigned int j = 0;j < (1 << m);++j){
		if((j & state[1]) == j && check(j)){
			for(unsigned int k = 0;k < (1 << m);++k){
				if((k & state[0]) == k && (j & k) == 0 && check(k)){
					dp[1][j][k] = ones[j] + ones[k];
				}
			}
		}
	}
	
	
	for(int line = 2;line < n;++line){
		int i = line % 3;
		for(int j = 0;j < (1 << m);++j){
			if((j & state[line]) == j && check(j)){
				for(int k = 0;k < (1 << m);++k){
					if(((k & state[line]) == k) && ((j & k) == 0) && check(k)){
						for(int g = 0;g < (1 << m);++g){
							if((g & state[line]) == g && check(g) && (g & j) == 0 && (g & k) == 0){
								dp[i][j][k] = max(dp[i][j][k],dp[((i - 1) % 3 + 3) % 3][k][g] + ones[j]);
							}
						}
					}
				}
			}
		}
	}
	
	unsigned int ans = 0;
	
	for(int i = 0;i < (1 << m);++i){
		if((i & state[n - 1]) == i && check(i)){
			for(int j = 0;j < (1 << m);++j){
				if((j & state[n - 2]) == j && check(j) && (i & j) == 0){
					ans = max(ans,dp[(((n - 1) % 3) + 3) % 3][i][j]);
				}
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}
2022/10/27 14:27
加载中...