状压dp(B - 炮兵阵地 POJ - 1185 )

2019-01-04 来源: Let_Life_Stop 发布在  https://www.cnblogs.com/letlifestop/p/10262747.html

题目链接:https://cn.vjudge.net/contest/276236#problem/B

题目大意:略

 具体思路:和我的上一篇写状压dp的思路差不多,不过就是这个题相当于上一个题的升级版,变成了左右,上下都会有限制,并且限制的步数是2,观察数据范围,如果按照上一个题的话,如果要是计算正确的范围取值的话,肯定会超时,所以我们可以先将所有的满足的情况先筛选出来,就算m取到10,总共的情况也就是60种,这样复杂度就大大的降下来了。

我们可以先预处理第一行和第二行,这样的话,我们就可以直接从第三行进行操作了,如果只是预处理第一行的话,第二行在往上走的时候,会取到第0行,而这一行我们是没有赋值的,所以我们应该预处理第一行和第二行。从第3行就可以直接进行操作了(就因为这个问题搞了一晚上。。。)。

我们开一个三维的dp数组,dp[i][j][k]。i代表的是第i行,j代表的是第i行取了哪种情况,k代表的是第i-1行的取值。

按道理来讲,我们应该一次比较三行的,可是为什么只是处理了两行?

因为我们在处理第i-1行的时候,我们比较的是dp[i-1][k][t]。这里的t是第i-2行,我们在处理第i行的时候就是按照一次比较三行来的,不过第三行的比较是通过第i-2行来进行比较的。

AC代码:

 #include<iostream>
 #include<cmath>
 #include<stack>
 #include<stdio.h>
 #include<algorithm>
 #include<queue>
 using namespace std;
 # define inf 0x3f3f3f3f
 # define ll long long
 +;
 char str[maxn];
 int a[maxn],ok[maxn],num[maxn];
 int dp[maxn][maxn][maxn];
 int cal(int t){
 ;
 while(t){
 ans+=(t&);
 t>>=;
 }
 return ans;
 }
 int main()
 {
     int n,m;
     scanf("%d %d",&n,&m);
     ; i<=n; i++)
     {
         scanf();
         ; j<=m; j++)
         {
             if(str[j]=='P')
                 a[i]=(a[i]<<)+;
             else
                 a[i]=(a[i]<<)+;
         }
     }
     <<m)-;
     ;
     ; i<=maxstate; i++)
     {
         )&i)==&&(((i>>)&i)==)&&(((i>>)&i)==)&&(((i>>)&i)==))//把合理的情况筛选出来。
         {
             ok[++ans]=i;
             num[ans]=cal(i);//记录一下当前的合理情况的能放的炮弹个数记录下来。
         }
     }
     ;
     ;i<=ans;i++){
     ])==ok[i]))
         dp[][i][]=num[i];
         maxx=max(maxx,dp[][i][]);
     }
     ;i<=ans;i++){
     ])==ok[i]){
     ;j<=ans;j++){
     )&&((ok[j]&a[])==ok[j])){
     dp[][i][j]=max(dp[][i][j],dp[][j][]+num[i]);
     maxx=max(maxx,dp[][i][j]);
     }
     }
     }
     }
     ;i<=n;i++){
     ;j<=ans;j++){
     if((ok[j]&a[i])==ok[j]){
     ;k<=ans;k++){
     )&&((ok[k]&a[i-])==ok[k])){
     ;l<=ans;l++){
     )&&((ok[l]&ok[j])==)&&((ok[l]&a[i-])==ok[l])){//在枚举第i-2行的时候,还需要和第i行和第i-1行进行比较。
     dp[i][j][k]=max(dp[i][j][k],dp[i-][k][l]+num[j]);
     maxx=max(maxx,dp[i][j][k]);
     }
     }
     }
     }
     }
     }
     }
     printf("%d\n",maxx);
     ;

 }
  

相关文章