算法分析
注意：题目中还有'H'位置不能放大炮，需要特殊标记一下，w[i]记录的是第i行能不能放大炮的状态，w[i]的二进制表示中，某位是1表示该位置不能放大炮，0表示该位置可以放大炮，当枚举到当前状态state时，若state & w[i] == 0表示合法
时间复杂度
上限复杂度是O(n∗s2∗k)，n表示行数，s表示合法状态数量，k表示合法状态的转移数量
参考文献
算法提高课
Java 代码
import java.util.ArrayList;
import java.util.Scanner;
public class Main {
static int N = 110,M = 1 << 10;
static int[] w = new int[N];
static int n , m;
static ArrayList<Integer> state = new ArrayList<Integer>();
static int[] cnt = new int[M];
static int[][][] f = new int[2][M][M];
static boolean check(int state)
{
for(int i = 0;i < m;i ++)
{
if((state >> i & 1) == 1 && ((state >> i + 1 & 1) == 1 || (state >> i + 2 & 1) == 1)) return false ;
}
return true;
}
static int count(int s)
{
int res = 0;
for(int i = 0;i < m;i ++)
if((s >> i & 1) == 1)
res ++;
return res;
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
m = scan.nextInt();
for(int i = 1;i <= n;i ++)
{
char[] g = scan.next().toCharArray();
int t = 0;
//不可填表示1，可填表示0
for(int j = 0;j < m;j ++)
{
if(g[j] == 'H') t += (1 << j);
}
w[i] = t;
}
//预处理出相邻不为1的状态
for(int i = 0; i < 1 << m;i ++)
{
if(check(i))
{
state.add(i);
cnt[i] = count(i);
}
}
for(int i = 1;i <= n;i ++)
for(int j = 0;j < state.size();j ++)//当前行
for(int k = 0;k < state.size();k ++)//倒数第二行
for(int u = 0;u < state.size();u ++)
{
int a = state.get(j);
int b = state.get(k);
int c = state.get(u);
if((a & b) != 0 || (a & c) != 0 || (b & c) != 0) continue;
if((w[i] & a) != 0 || (w[i - 1] & b) != 0) continue;
f[i & 1][j][k] = Math.max(f[i & 1][j][k], f[i - 1 & 1][k][u] + cnt[a]);
}
int res = 0;
for(int i = 0;i < state.size();i ++)
for(int j = 0;j < state.size();j ++)
res = Math.max(res,f[n & 1][i][j]);
System.out.println(res);
}
}
为啥要把i-1行放在dp循环最外面，然后再是第i和第i-2行，按理来说不应该第i行在最外面吗，这样的话可以保证枚举到第i行时第i-1行已被算过
同问
有一个地方没有看懂，枚举的时候分别枚举当前行，上一行，上上行三个状态，为什么在检查和w[]是否有冲突的时候上上行没有检查，而只检查当前行和上一行
有人问过，就搬过来了hh
这行实际上是检查当前行摆放是否合法。所以每行只需被检测一次即可。
检查g[i] & b时，g[i - 1] & a被上次循环，g[i - 2] : 0) & c被上上次循环检测过了。若非法相应的 f 必为0。
加多这个
if(i >= 2 && (w[i - 2] & c) != 0) continue;也可以的感谢解惑，我本来也是增加了 i >= 2 的判断，看了你的回答之后，我只保留了对当前行的检查 也是可以的
import java.util.*; import java.io.*; class Main { static int n, m; static boolean check(int u) { for (int i = 0; i < m; i++) { int i1 = ((u >> i) & 1); int i2 = ((u >> (i + 1)) & 1); int i3 = ((u >> (i + 2)) & 1); if (i1 + i2 + i3 > 1) { return false; } } return true; } static int count(int u) { int ans = 0; for (int i = 0; i < m; i++) { if (((u >> i) & 1) == 1) ans++; } return ans; } public static void main(String[] args) throws IOException { BufferedReader r = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter w = new BufferedWriter(new OutputStreamWriter(System.out)); String[] s = r.readLine().split(" "); n = Integer.parseInt(s[0]); m = Integer.parseInt(s[1]); int[] arr = new int[n + 1]; for (int i = 1; i <= n; i++) { s = r.readLine().split(""); int num = 0; for (int j = 0; j < m; j++) { if (s[j].equals("H")) { num += 1 << j; } } arr[i] = num; } List<Integer> list = new ArrayList<>(); Map<Integer, Integer> map = new HashMap<>(); // 预处理出合理的行 for (int i = 0; i < 1 << m; i++) { if (check(i)) { list.add(i); map.put(i, count(i)); } } int len = list.size(); int ans = 0; int[][][] f = new int[2][len][len]; // f(i,j,k) 代表考虑前i行，第i-1行状态为j下标对应的值，第i行状态为k下标对应的值 for (int i = 1; i <= n; i++) { for (int j = 0; j < len; j++) { // i for (int k = 0; k < len; k++) { // i - 1 for (int u = 0; u < len; u++) { // i - 2 int a = list.get(j), b = list.get(k), c = list.get(u); if ((a & b) != 0 || (a & c) != 0 || (b & c) != 0) continue; int a1 = arr[i], b1 = arr[i - 1]; // 理论上每一行都会被检查，所以只检查当前行就可以了，而无须检查第 i - 1 和 i - 2 行 if ((a & a1) != 0) continue; f[i & 1][k][j] = Math.max(f[i & 1][k][j], f[i - 1 & 1][u][k] + map.get(a)); ans = Math.max(ans, f[i & 1][k][j]); } } } } w.write(ans + " "); w.flush(); r.close(); w.close(); } }可是如果是非法的 f=0加上cnt[]后还是可能会更新当前值的吧
想请问一下为什么这个题和玉米田的题目都是只跟下标i-1的状态有关，但玉米田的那个题不能用滚动数组呢
也是可以用的，因为第
i行只会用到第i-1行的数据这是后面直接用值作为位置写的，和题解的有小小不同，原理是一样的
炮兵阵列：
#include <iostream> #include <algorithm> #include <vector> #include <cstring> using namespace std; const int N = 110, M = 1 << 10; int n, m; int f[2][M][M]; vector<int> state; int w[N]; int cnt[M]; bool check(int s) { for(int i = 0;i < m;i ++) { if((s >> i & 1) == 1 && ((s >> (i + 1) & 1) == 1 || (s >> (i + 2) & 1) == 1)) return false; } return true; } int count(int s) { int res = 0; for(int i = 0;i < m;i ++) { if((s >> i & 1) == 1) res ++; } return res; } int main() { cin >> n >> m; for(int i = 1;i <= n;i ++) { int t = 0; for(int j = 0;j < m;j ++) { char c; cin >> c; if(c == 'H') t += 1 << j; } w[i] = t; } for(int i = 0;i < 1 << m;i ++) { if(check(i)) { state.push_back(i); cnt[i] = count(i); } } for(int i = 1;i <= n;i ++) { for(int j = 0;j < state.size();j ++) { for(int k = 0;k < state.size();k ++) { for(int u = 0;u < state.size();u ++) { int a = state[j], b = state[k], c = state[u]; if((a & b) != 0 || (a & c) != 0 || (b & c) != 0) continue; if((w[i] & a) != 0 || (w[i - 1] & b) != 0) continue; if(i >= 2 && (w[i - 2] & c) != 0) continue; f[i & 1][a][b] = max(f[i & 1][a][b], f[i - 1 & 1][b][c] + cnt[a]); } } } } int res = 0; for(int j = 0;j < state.size();j ++) for(int k = 0;k < state.size();k ++) { int a = state[j], b = state[k]; res = max(res, f[n & 1][a][b]); } cout << res << endl; return 0; }玉米田：
#include <iostream> #include <algorithm> #include <vector> using namespace std; const int N = 13, M = 1 << 12 , mod = 100000000; int n, m; int f[2][M]; int row[N];//记录每一行土地发育的状态 vector<int> state;//可行的状态 vector<int> head[M];//表示与M状态可以搭配的有什么状态 bool check(int s) { for(int i = 0;i < m - 1;i ++) { if(((s >> i) & 1 == 1) && ((s >> (i + 1) & 1 == 1))) return false; } return true; } int main() { cin >> n >> m; for(int i = 1;i <= n;i ++) { int t = 0; for(int j = 0;j < m;j ++) { int x; cin >> x; if(x == 0) t += 1 << j; } row[i] = t; } for(int i = 0;i < 1 << m;i ++) if(check(i)) state.push_back(i); for(int i = 0;i < state.size();i ++) for(int j = 0;j < state.size();j ++) { int a = state[i], b = state[j]; if((a & b) == 0) { head[a].push_back(b); } } f[0][0] = 1; for(int i = 1;i <= n + 1;i ++) { for(int a = 0;a < state.size();a ++) { f[i & 1][state[a]] = 0;//这个必须加 if((row[i] & state[a]) == 0) { for(int b = 0;b < head[state[a]].size();b ++) { f[i & 1][state[a]] = (f[i & 1][state[a]] + f[i - 1 & 1][head[state[a]][b]]) % mod; } } } } long long res = 0; for(int i = 0;i < 1 << m;i ++) res = (res + f[n & 1][i]) % mod; cout << res << endl; return 0; }谢谢大佬，我明白了，玉米田这道题在开始新的行的时候必须得把当前行的值都清空，不然会受到上一行的影响，也就是f[i & 1][state[a]] = 0;必须得有。
是的
f[i & 1][j][k] = Math.max(f[i & 1][j][k], f[i - 1 & 1][k][u] + cnt[a]);
这个地方，会不会存在可能，f[i & 1][j][k]存储的上一次最大值比现在所有的f[i - 1 & 1][k][u] + cnt[a]都要大，举个例子，i=5的时候，记录了一个f[5 & 1][j][k]，到i=7的时候，会不会所有的f[6 & 1][k][u] + cnt[a]都比f[5 & 1][j][k]小，这样第七行存储的值其实是第五行的状态呀
会，第5层的集合的最大值会给第6层，第6层集合的最大值会给第7层