O2已过,求教如何降低时间复杂度
查看原帖
O2已过,求教如何降低时间复杂度
255762
lyxleo楼主2022/7/4 14:46
#include <bits/stdc++.h>
using namespace std;
int n,m;
int state[101];
long long dp[101][1<<10][1<<10];
inline bool check(int x);
inline int count_num(int x);
inline bool fit(int x,int y){
	return (x & y) == 0;
}
inline bool in(int line,int x){
	return (x & state[line]) == x;
}
int num;
int main(){
	scanf("%d %d",&n,&m);
	for(int i = 1;i <= n;++i){
		for(int j = 0;j < m;++j){
			char c;
			scanf(" %c",&c);
			if(c == 'P'){
				state[i] |= (1 << j);
			}
		}
	}
	state[0] = (1 << 10) - 1;
	for(int i = state[1];i;i = (i - 1) & state[1]){
		if(check(i)){
			num = count_num(i);//Calculate the quantity of 1
			for(int j = 0;j < (1 << m);++j){
				dp[1][i][j] = num;
			}
		}
	}
	for(int line = 2;line <= n;++line){
		for(int i = 0;i < (1 << m);++i){
			if(check(i) && in(line,i)){
				int num = count_num(i);
				for(int j = 0;j < (1 << m);++j){
					if(check(j) && in(line-1,j) && fit(i,j)){
						for(int k = 0;k < (1 << m);++k){
							if(in(line-2,k) && check(k) && fit(j,k) && fit(i,k)){
								dp[line][i][j] = max(dp[line][i][j],dp[line-1][j][k] + num);
							} 
						}
					}
				}
			}
		}
	}
	long long ans = -1;
	for(int i = 0;i < (1 << m);++i){
		if(check(i) && in(n,i)){
			for(int j = 0;j < (1 << m);++j){
				if(check(j) && in(n-1,j)){
					ans = max(ans,dp[n][i][j]);
				}
			}
		}
	}
	printf("%lld",ans);
	return 0;
}

inline bool check(int x){//Check for errors in line x
	return (((x >> 1) & x) == 0 && ((x >> 2) & x) == 0);
}

inline int count_num(int x){//ditto
	int cnt = 0;
	while(x){
		if(x & 1){
			++cnt;
		}
		x >>= 1;
	}
	return cnt;
}
2022/7/4 14:46
加载中...