1 条题解

  • 0
    @ 2025-4-7 18:48:35

    解题思路

    算法设计

    采用三维动态规划结合状态压缩技术解决炮兵布阵问题:

    核心思想

    • 三维DP设计:dp[i][j][k]表示前i行中,第i行状态为j,第i-1行状态为k时的最大炮兵数量
    • 状态压缩:将每行地形和炮兵部署状态用二进制数表示

    状态表示方法

    地形 二进制 十进制
    PHPP 0100 4
    PPHH 0011 3
    PPPP 0000 0
    PHHP 0110 6

    实现步骤

    1. 预处理
      • 将地图每行转换为二进制数(高地为1,平地为0)
      • 生成所有合法单行状态state[]
      • 计算每个状态的炮兵数量soldier[]
    2. 状态转移
      • 检查三行状态是否冲突:(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
    上传者