POJ 1185 炮兵阵地 dp三维和二维的区别状压dp

偏执的太偏执、 2023-06-16 10:34 16阅读 0赞

**参考：**  
**[https://www.cnblogs.com/scau20110726/archive/2013/02/27/2935256.html][https_www.cnblogs.com_scau20110726_archive_2013_02_27_2935256.html]**

**二维的dp**  
**最开始写了的dp数组是二维的，想法也很简单**  
**dp\[r\]\[i\]表示：第r行取i状态的时候，i行以及以上的行一共有多少士兵**

**状态转移：**

dp[r][i] = max(dp[r][i], dp[r-2][k] + cntSol[j]+ cntSol[i]);
    
    cntSol[i] 表示第i个状态有几个士兵

**但是一直wa，但是不明白开三维数组的作用。**

**这样的写法，可以保证第r行和前两行的不冲突，但是在对i行的状态的进行变化的时候，会影响r-1行的状态，进而影响r-2行的状态，这个时候dp\[r-2\]\[k\]应该随着j的变化而变化的，也就是说r行的计算会影响子问题的最优解，不满足动态规划的最优子结构**

**也就说我们在考虑第r行的时候，取了dp\[r-2\]\[k\] + cntSol\[j\]+ cntSol\[i\]里面的j、k组合里面的最大值，把dp\[r-2\]\[k\]当做一个定值来计算，但其实这个值会随着r-1行的变化而变化**

#include <iostream>
    #include <stdio.h>
    #include <string.h>
    #include <stack>
    #include <string>
    
    using namespace std;
    
    #define debug(x) cout<<#x<<": "<<x<<endl;
    
    char tempG[11];
    int bitG[101];
    int cntSol[101];
    int sol[70];
    int maxSol = 0;
    int dp[101][70];
    
    int N,M;
    
    int cnt1(int a){ 
        int ret = 0;
        while( a>0 ){ 
            ret++;
            a&=(a-1);
        }
        return ret;
    }
    
    int findw(){ 
        int ret = 0;
        for(int i = 0; i<(1<<M);i++){ 
            if( i&(i<<1) || i&(i<<2) ){ 
                continue;
            }
            sol[maxSol] = i;
            cntSol[maxSol] = cnt1(i);
            maxSol++;
        }
    
        if( N>0 ){ 
    
            for(int i=0;i<maxSol;i++){ 
    
                if( bitG[0]&sol[i] )continue;
    
                dp[0][i] = cntSol[i];
                ret = max(ret,dp[0][i]);
            }
        }
    
        if(N>1){ 
            for(int i=0;i<maxSol;i++){ 
                for(int j=0;j<maxSol;j++){ 
                    if( bitG[0]&sol[j] )continue;
                    if( bitG[1]&sol[i] ) continue;
                    if( sol[i]&sol[j] ) continue;
                    dp[1][i] = max(dp[1][i], dp[0][j] + cntSol[i]);
                    ret = max(ret,dp[1][i]);
                }
            }
        }
    
        for(int r = 2; r < N; r ++){ 
            for(int i=0;i<maxSol;i++){ 
    
                if(bitG[r]&sol[i])continue;
    
                for(int j = 0;j < maxSol;j ++){ 
    
                    if(bitG[r-1]&sol[j])continue;
                    if(sol[i]&sol[j])continue;
    
                    for(int k = 0;k < maxSol;k ++){ 
    
                        if(bitG[r-2]&sol[k])continue;
    
                        if(sol[i]&sol[k])continue;
                        if(sol[k]&sol[j])continue;
    
                        //dp[r][i]= max (dp[r][i], dp[r-1][j]+dp[r-2][k]) + cntSol[i];
    
                        dp[r][i] = max(dp[r][i], dp[r-2][k] + cntSol[j]+ cntSol[i]);
    
                        //dp[r][i] = max(dp[r][i], dp[r-1][j] + cntSol[i]);
    
                        ret = max(ret,dp[r][i]);
                    }
                }
            }
        }
        return ret;
    }
    
    **CODE**
    int main()
    { 
    
        while(scanf("%d%d",&N,&M) != EOF){ 
            //scanf("%d%d",&N,&M);
            memset(bitG,0,sizeof(bitG));
            memset(dp,0,sizeof(dp));
            memset(cntSol,0,sizeof(cntSol));
            maxSol = 0;
    
            for(int i=0;i<N;i++){ 
                scanf("%s",tempG);
                for(int j=0;j<M;j++){ 
                    if( tempG[j]=='H' ){ 
                        bitG[i] += (1<<j);
                    }
                }
            }
    
            int ret = findw();
            //disp();
    
            printf("%d\n",ret);
        }
        return 0;
    }
    
    /* 5 4 HHHH HHHH HHHH HHHH HHHH 5 4 PHHH HHHP HHHH PHHH HHHP 5 4 PPPP PPPP PPPP PPPP PPPP 5 4 PHPP PPHH PPPP PHPP PHHP 1 4 PPPP 0 0 1 10 PPPPPPPPPP 2 10 PPPPPPPPPP PPPPPPPPPP 8 10 PPPPPPPPPP PPPPPPPPPP PPPPPPPPPP PPPPPPPPPP PPPPPPPPPP PPPPPPPPPP PPPPPPPPPP PPPPPPPPPP */

#include <iostream>
    #include <stdio.h>
    #include <string.h>
    #include <stack>
    #include <string>
    
    using namespace std;
    
    #define debug(x) cout<<#x<<": "<<x<<endl;
    
    char tempG[11];
    int bitG[101];
    int cntSol[101];
    int sol[70];
    int maxSol = 0;
    int dp[101][70][70];
    
    int N,M;
    
    int cnt1(int a){ 
        int ret = 0;
        while( a>0 ){ 
            ret++;
            a&=(a-1);
        }
        return ret;
    }
    
    
    int findw(){ 
        int ret = 0;
        for(int i = 0; i<(1<<M);i++){ 
            if( i&(i<<1) || i&(i<<2) ){ 
                continue;
            }
            sol[maxSol] = i;
            cntSol[maxSol] = cnt1(i);
            maxSol++;
        }
        
        if( N>0 ){ 
                
            for(int i=0;i<maxSol;i++){ 
                    
                if( bitG[0]&sol[i] )continue;
    
                dp[0][i][0] = cntSol[i];
                ret = max(ret,dp[0][i][0]);
            }
        }
    
        if(N>1){ 
            for(int i=0;i<maxSol;i++){ 
                for(int j=0;j<maxSol;j++){ 
                    if( bitG[0]&sol[j] )continue;
                    if( bitG[1]&sol[i] ) continue;
                    if( sol[i]&sol[j] ) continue;
                    dp[1][i][j] = max(dp[1][i][j], dp[0][j][0] + cntSol[i]);
                    ret = max(ret,dp[1][i][j]);
                }
            }
        }
    
        for(int row = 2;row < N; row ++){ 
            for(int i=0;i<maxSol;i++){ 
    
                if(bitG[row]&sol[i])continue;
    
                for(int j = 0;j < maxSol;j ++){ 
    
                    if(bitG[row-1]&sol[j])continue;
                    if(sol[i]&sol[j])continue;
    
                    for(int k = 0;k < maxSol;k ++){ 
    
                        if(bitG[row-2]&sol[k])continue;
    
                        if(sol[i]&sol[k])continue;
                        if(sol[k]&sol[j])continue;
    
                        dp[row][i][j] = max(dp[row][i][j], dp[row-1][j][k] + cntSol[i]);
    
                        ret = max(ret,dp[row][i][j]);
                    }
                }
            }
        }
        return ret;
    }
    
    
    int main()
    { 
    
        while(scanf("%d%d",&N,&M) != EOF){ 
            //scanf("%d%d",&N,&M);
            memset(bitG,0,sizeof(bitG));
            memset(dp,0,sizeof(dp));
            memset(cntSol,0,sizeof(cntSol));
            maxSol = 0;
    
            for(int i=0;i<N;i++){ 
                scanf("%s",tempG);
                for(int j=0;j<M;j++){ 
                    if( tempG[j]=='H' ){ 
                        bitG[i] += (1<<j);
                    }
                }
            }
    
            int ret = findw();
            //disp();
    
            printf("%d\n",ret);
        }
        return 0;
    }
    /* 5 4 HHHH HHHH HHHH HHHH HHHH 5 4 PHHH HHHP HHHH PHHH HHHP 5 4 PPPP PPPP PPPP PPPP PPPP 5 4 PHPP PPHH PPPP PHPP PHHP 1 4 PPPP 0 0 1 10 PPPPPPPPPP 2 10 PPPPPPPPPP PPPPPPPPPP 6 10 PPPPPPPPPP PPPPPPPPPP PPPPPPPPPP PPPPPPPPPP PPPPPPPPPP PPPPPPPPPP */

![在这里插入图片描述][20191125203849124.png]

[https_www.cnblogs.com_scau20110726_archive_2013_02_27_2935256.html]: https://www.cnblogs.com/scau20110726/archive/2013/02/27/2935256.html
[20191125203849124.png]: https://img-blog.csdnimg.cn/20191125203849124.png