poj2352，POJ 1185 炮兵陣地（狀壓dp）

2023-11-18 阅读 28 评论 0

摘要：? http://poj.org/problem?id=1185 poj2352，題意： ? 狀壓dp入門，思路：每一行最多只有10列，所以可以用二進制來表示每一行的狀態。 d【i】【j】【k】表示第i行狀態為k時，并且上一行狀態為j時的最大炮兵數。 1 #include<iostream> 2 #

http://poj.org/problem?id=1185

poj2352，題意：

狀壓dp入門，思路：

每一行最多只有10列，所以可以用二進制來表示每一行的狀態。

d【i】【j】【k】表示第i行狀態為k時，并且上一行狀態為j時的最大炮兵數。

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<cstring>
  4 #include<cstdio>
  5 #include<sstream>
  6 #include<vector>
  7 #include<stack>
  8 #include<queue>
  9 #include<cmath>
 10 #include<map>
 11 #include<set>
 12 using namespace std;
 13 typedef long long ll;
 14 typedef pair<int,int> pll;
 15 const int INF = 0x3f3f3f3f;
 16 const int maxn = 20+5;
 17 
 18 int n, m;
 19 
 20 char s[20];
 21 int st[105];
 22 int tmp[105];
 23 int num[105];
 24 int d[105][105][105];
 25 
 26 int calc(int x)
 27 {
 28     int tmp=0;
 29     while(x)
 30     {
 31         if(x&1)  tmp++;
 32         x>>=1;
 33     }
 34     return tmp;
 35 }
 36 
 37 int main()
 38 {
 39     //freopen("in.txt","r",stdin);
 40     while(~scanf("%d%d",&n, &m))
 41     {
 42         getchar();
 43         for(int i=1;i<=n;i++)
 44         {
 45             scanf("%s",&s);
 46             st[i]=0;
 47             for(int j=0;j<m;j++)
 48             {
 49                 st[i]=(st[i]<<1)|(s[j]=='P');
 50             }
 51         }
 52 
 53         int top=0;
 54         for(int i=0;i<(1<<m);i++)  //記錄可行狀態
 55         {
 56             if(!(i&(i<<1)) && !(i&(i<<2)))
 57             {
 58                 tmp[top]=i;
 59                 num[top]=calc(i);
 60                 top++;
 61             }
 62         }
 63 
 64         int ans=0;
 65         memset(d,-1,sizeof(d));
 66         for(int i=0;i<top;i++)  //第一行狀態
 67         {
 68             if((st[1]|tmp[i])==st[1])   d[1][0][i]=num[i];
 69         }
 70 
 71         for(int i=2;i<=n;i++)
 72         {
 73             for(int j=0;j<top;j++)  //第i行狀態
 74             {
 75                 if((st[i]|tmp[j])!=st[i])  continue;
 76 
 77                 for(int k=0;k<top;k++)  //第i-1行狀態
 78                 {
 79                     if((st[i-1]|tmp[k])!=st[i-1])  continue;
 80                     if(tmp[j]&tmp[k])  continue;  //和第i行有沖突
 81 
 82                     for(int t=0;t<top;t++)  //第i-2行狀態
 83                     {
 84                         if(i>2)
 85                         {
 86                             if((st[i-2]|tmp[t])!=st[i-2])  continue;
 87                             if(tmp[t]&tmp[k])  continue;
 88                             if(tmp[t]&tmp[j])  continue;
 89                         }
 90 
 91                         d[i][k][j]=max(d[i][k][j],d[i-1][t][k]+num[j]);
 92                     }
 93                 }
 94             }
 95         }
 96         
 97         for(int i=0;i<top;i++)
 98             for(int j=0;j<top;j++)
 99             ans=max(ans,d[n][i][j]);
100         printf("%d\n", ans);
101     }
102     return 0;
103 }