[状压dp]POJ1185 炮兵阵地

时间：2022-07-06 03:35:23

中文题 题意不再赘述

[状压dp]POJ1185 炮兵阵地

对于中间这个“P” 根据dp的无后效性 我们只需考虑前面的

就变成了 只需考虑：

[状压dp]POJ1185 炮兵阵地

也就是状压前两行

具体与HDOJ的4539类似： 看HDOJ 4539

仅仅是共存状态的判断不同

 //#include <bits/stdc++.h>

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 typedef long long LL;

 int dp[][][], mp[][];

 int pos[], d;

 int main()

 {

     int d=;

     for(int i=;i<(<<);i++)

         if(!(i&(i<<)) && !(i&(i<<)))

             pos[d++]=i;// 预处理 一行 符合条件的

     int n, m;

     while(~scanf("%d%d", &n, &m))

     {

         int ans=;

         memset(mp, , sizeof(mp));

         for(int i=;i<=n;i++)

             for(int j=;j<m;j++)

             {

                 char c;

                 cin>>c;

                 mp[i][j]=(c=='P');

             }

         memset(dp, , sizeof(dp));

         for(int i=;i<=n;i++)//枚举n行

             for(int j=;j<d && pos[j]<(<<m);j++)

             {

                 int sum=;

                 for(int k=;k<m;k++)//对于当前(i,k位置)该行(前面k格)是否满足

                     if(pos[j]&<<k)

                         sum+=mp[i][k];

                 for(int k=;k<d && pos[k]<(<<m);k++) // 枚举i-1行的状态 看能否与第i行共存

                     if(!(pos[j]&pos[k]))

                     {

                         int tmp=;

                         for(int l=;l<d && pos[l]<(<<m);l++)  // 枚举i-2行的状态 看能否与第i行、第i-1行共存

                             if(!(pos[j]&pos[l]))

                                 tmp=max(tmp, dp[-i&][k][l]);

                         dp[i&][j][k]=tmp+sum;

                         ans=max(ans, dp[i&][j][k]);

                     }

             }

         printf("%d\n", ans);

     }

     return ;

 }

POJ 1185

相关文章