算法实验T14——POJ 1185炮兵阵地

本文主要是介绍算法实验T14——POJ 1185炮兵阵地，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

思路

        一道非常好的状压DP题。

        首先我们从题目中总结出约束条件：

•         炮不能安置在山上；
•         一行内的炮不能相距小于2个距离；
•         一列的炮不能相距小于2个距离；

        注意到地形图只有山和平原两种状态，可以用 1 和 0 来表示，因此每一行就是一个最多10位的二进制串转化成10进制对应1024种状态。这里我们用1来表示山，更方便后面处理。

        而对于炮兵的安置方案，对于每一个位置，也是放和不放两个状态，我们也可以转化为二进制串，1表示放炮兵。

        以上其实就完成了状态压缩，现在我们可以用串的运算来翻译约束条件，设a[0...n-1]表示每一行的地形状态，设 S、L、LL依次表示第 i 行、第（i - 1）行、第(i - 2)行炮兵安置状态。

        炮兵不能安置在山上，其实就等价翻译为

                        

         一行内的炮不能相距小于2个距离，等价翻译为 

                        

         一列的炮不能相距小于2个距离，等价翻译为

                        

        我们发现，如果只考虑前 i 行的话，那么第 i 行的方案仅由其前两行和自身约束，且具有最优子结构，所以我们考虑用DP。

        DP数组，DP[L][S][i]表示上行状态为L，本行状态为S的情况下，前 i 行的最优解。

        那么对于每一行，我们枚举其前两行和当前行的所有符合约束的状态，有状态转移方程，其中sum[S]表示S状态放置了多少个炮兵，其实就是统计该二进制串1的个数。

        最后的答案就是最后一行的倒数第二行的所有状态中DP[L][S][n-1]最大的一个。

        在实现时有两点需要注意：

1.         DP数组最后一维实际上不需要 n 的大小，只需要3的大小，循环使用即可。
2.         一定要事先筛选出那些自身满足 “一行内的炮不能相距小于2个距离” 这一条件的状态，用一个数组存下来。因为这个约束和地形、其他行状态都无关，哪些是符合的一开始就是恒定的，如果每次都在循环里面去判断，会重复浪费很多时间，POJ上会TLE。

AC代码

#include<iostream>
#include<cstdio>
using namespace std;
int a[1<<10], dp[1<<10][1<<10][3], sum[1<<10], cddt[1<<10], len_cddt;
int getsum(int x){int cnt = 0;while(x){if(x & 1) cnt++;x >>= 1; }return cnt;
}
int main(){int n, m;char x;scanf("%d%d", &n, &m);for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){cin>>x;a[i] <<= 1; a[i] += (x == 'H' ? 1 : 0); }}for(int i = 0; i < (1 << m); i++){sum[i] = getsum(i);}for(int i = 0; i < (1<<m); i++){if( ( i & (i << 1) ) || ( i & (i << 2) ) )continue;cddt[len_cddt++] = i;}//先将一行内不会互相攻击到的状态筛选出来for(int i = 0; i < len_cddt; i++){if( cddt[i] & a[0] ) continue;dp[0][cddt[i]][0] = sum[cddt[i]];}//初始化第0行for(int i = 0; i < len_cddt; i++){if( cddt[i] & a[0] )continue;for(int j = 0; j < len_cddt; j++){if( ( cddt[j] & a[1] ) || (cddt[i] & cddt[j]) )continue;dp[cddt[i]][cddt[j]][1] = sum[cddt[j]] + sum[cddt[i]];}}//初始化第1行for(int i = 2; i < n; i++){for(int s = 0; s < len_cddt; s++){if( ( cddt[s] & a[i] ) )continue;for(int l = 0; l < len_cddt; l++){if( ( cddt[l] & a[i - 1] ) || ( cddt[l] & cddt[s] ) )continue;for(int ll = 0; ll < len_cddt; ll++){if( ( cddt[ll] & a[i - 2] ) || ( cddt[ll] & cddt[l] ) || ( cddt[ll] & cddt[s] ) )continue;dp[cddt[l]][cddt[s]][i % 3] = max(dp[cddt[l]][cddt[s]][i % 3], dp[cddt[ll]][cddt[l]][(i - 1)%3] + sum[cddt[s]]);}}}}int res = 0;for(int l = 0; l < len_cddt; l++){for(int s = 0; s < len_cddt; s++){res = max(res, dp[cddt[l]][cddt[s]][(n - 1) % 3]);}}printf("%d", res);return 0;
}

这篇关于算法实验T14——POJ 1185炮兵阵地的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---