1 条题解
-
0
解题思路
算法设计
采用三维动态规划结合状态压缩技术解决炮兵布阵问题:
核心思想
- 三维DP设计:dp[i][j][k]表示前i行中,第i行状态为j,第i-1行状态为k时的最大炮兵数量
- 状态压缩:将每行地形和炮兵部署状态用二进制数表示
状态表示方法
地形 二进制 十进制 PHPP 0100 4 PPHH 0011 3 PPPP 0000 0 PHHP 0110 6 实现步骤
- 预处理:
- 将地图每行转换为二进制数(高地为1,平地为0)
- 生成所有合法单行状态state[]
- 计算每个状态的炮兵数量soldier[]
- 状态转移:
- 检查三行状态是否冲突:(state[j] & state[k]) || (state[j] & state[p]) || (state[k] & state[p])
- 更新DP值:dp[i][j][k] = max(dp[i][j][k], dp[i-1][k][p] + soldier[j])
关键优化
- 合法性检查:使用位运算快速判断状态是否合法
- 空间优化:利用滚动数组减少空间消耗
- 剪枝策略:预处理排除不可能的状态组合
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define maxr 110 #define maxc 15 #define maxm 70 #define CL(a) memset(a,0,sizeof(a)) bool legal(int a, int b){ return a&b; } int row, col; int nums; int base[maxr]; int state[maxm], soldier[maxm]; int dp[maxr][maxm][maxm];//第i行为j状态,i-1行为k状态,最大炮兵个数dp[i][j][k] int main() { //freopen("in.txt", "r", stdin); CL(base); CL(state); CL(soldier); CL(dp); nums = 0; char str[2][maxc]; scanf("%d %d", &row, &col); for (int i = 0; i < row; i++) //将地图转换成二进制 { scanf("%s", str[0]); for (int j = 0; j < col;j++) if (str[0][j] == 'H') base[i] += 1 << j; } for (int i = 0; i < (1<<col); i++){ //确立仅仅是两个炮兵互不攻击的状态 if (legal(i, i << 2) || legal(i, i << 1)) continue; //dont forget case: d=1 int k = i; while (k){ soldier[nums] += k & 1; k = k >> 1; } state[nums++] = i; } for (int i = 0; i < nums; i++) //初始化 { if (legal(state[i], base[0])) continue; //去除炮兵在山上的 dp[0][i][0] = soldier[i]; } for (int r = 1; r < row; r++) //每一行 { for (int i = 0; i < nums; i++) //第i行状态 { if (legal(state[i], base[r])) continue; //去除炮兵在山上的 for (int j = 0; j < nums; j++) //第i-1行状态 { if (legal(state[j], base[r-1])) continue; //去除炮兵在山上的 if (legal(state[i], state[j])) continue; //除去上下两行相互攻击 for (int k = 0; k < nums; k++) //第i-2行状态 { if (r - 2 >= 0 && legal(state[k], base[r - 2])) continue; //去除炮兵在山上的 if (legal(state[i], state[k])) continue; //除去上下两行相互攻击 if (legal(state[j], state[k])) continue; //除去上隔一行下两行相互攻击 dp[r][i][j] = max(dp[r][i][j], dp[r - 1][j][k] + soldier[i]); } } } } int ans = 0; for (int i = 0; i < nums; i++) for (int j = 0; j < nums; j++) ans = max(ans, dp[row - 1][i][j]); printf("%d\n", ans); return 0; }
- 1
信息
- ID
- 186
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 2
- 已通过
- 1
- 上传者