题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
import java.util.*;
public class Main {
static int n;
static int m;
static int N=1<<10;
static List<Integer>state=new ArrayList<Integer>();//记录所有的合法状态
static int[]cnt=new int[N];//记录合法状态的1的数量
static int[][][]f=new int[2][N][N];
static int[]a=new int[110];
static boolean check(int st){
int lasti=-2;
for(int i=1;i<=m;i++){
int k=st>>(i-1);
if((k&1)==1){
if(i-lasti<3){
return false;
}
lasti=i;
}
}
return true;
}
static int count(int st){
int cnt=0;
for(int i=0;i<m;i++){
if((st>>i&1)==1){
cnt++;
}
}
return cnt;
}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
n=sc.nextInt();
m=sc.nextInt();
for(int i=1;i<=n;i++){
String str=sc.next();
int s=0;
for(int j=1;j<=m;j++){
int c=str.charAt(j-1)=='P'?0:1;
if(c==1){
s+=1<<(j-1);
}
}
a[i]=s;
}
//预处理 枚举所有的合法状态 数量很少
for(int i=0;i<(1<<m);i++) {
if (check(i)) {
state.add(i);
cnt[i] = count(i);
}
}
for(int i=1;i<=n+2;i++){
for(int k:state){
for(int j:state){
for(int u:state){
if((k&j)!=0||(k&u)!=0||(j&u)!=0){
continue;
}
if((a[i]&k)!=0){
continue;
}
//滚动数组 只需要开2行就行
f[i&1][k][j]=Math.max(f[i&1][k][j],f[(i-1)&1][j][u]+count(k));
}
}
}
}
System.out.println(f[(n+2)&1][0][0]);
}
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla