POJ 1185 炮兵阵地（状压dp）

短命女 2022-05-28 09:27 124阅读 0赞

<table style="background-image:url(&quot;http://poj.org/images/table_back.jpg&quot;);font-family:'Microsoft YaHei';"> 
 <tbody> 
  <tr> 
   <td> 
    <div style="text-align:center;font-family:Arial, Helvetica, sans-serif;font-size:18pt;font-weight:bold;color:#0000FF;">
      炮兵阵地 
    </div> 
    <div style="text-align:center;font-family:Arial, Helvetica, sans-serif;font-size:12pt;"> 
     <table> 
      <tbody> 
       <tr> 
        <td><strong>Time Limit:</strong>&nbsp;2000MS</td> 
        <td>&nbsp;</td> 
        <td><strong>Memory Limit:</strong>&nbsp;65536K</td> 
       </tr> 
       <tr> 
        <td><strong>Total Submissions:</strong>&nbsp;30877</td> 
        <td>&nbsp;</td> 
        <td><strong>Accepted:</strong>&nbsp;11922</td> 
       </tr> 
      </tbody> 
     </table> 
    </div><p style="font-family:Arial, Helvetica, sans-serif;font-size:18pt;font-weight:bold;color:#0000FF;">Description</p> 
    <div style="font-family:'Times New Roman', Times, serif;font-size:12pt;">
      司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成，地图的每一格可能是山地（用"H" 表示），也可能是平原（用"P"表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示：&nbsp; 
     <br>  
     <img src="http://poj.org/images/1185_1.jpg" alt="">  
     <br>如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。&nbsp; 
     <br>现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。&nbsp; 
     <br> 
    </div><p style="font-family:Arial, Helvetica, sans-serif;font-size:18pt;font-weight:bold;color:#0000FF;">Input</p> 
    <div style="font-family:'Times New Roman', Times, serif;font-size:12pt;">
      第一行包含两个由空格分割开的正整数，分别表示N和M；&nbsp; 
     <br>接下来的N行，每一行含有连续的M个字符('P'或者'H')，中间没有空格。按顺序表示地图中每一行的数据。N &lt;= 100；M &lt;= 10。 
    </div><p style="font-family:Arial, Helvetica, sans-serif;font-size:18pt;font-weight:bold;color:#0000FF;">Output</p> 
    <div style="font-family:'Times New Roman', Times, serif;font-size:12pt;">
      仅一行，包含一个整数K，表示最多能摆放的炮兵部队的数量。 
    </div><p style="font-family:Arial, Helvetica, sans-serif;font-size:18pt;font-weight:bold;color:#0000FF;">Sample Input</p><pre style="font-family:'Courier New', Courier, monospace;font-size:12pt;">5 4
PHPP
PPHH
PPPP
PHPP
PHHP</pre><p style="font-family:Arial, Helvetica, sans-serif;font-size:18pt;font-weight:bold;color:#0000FF;">Sample Output</p><pre style="font-family:'Courier New', Courier, monospace;font-size:12pt;">6</pre><p style="font-family:Arial, Helvetica, sans-serif;font-size:18pt;font-weight:bold;color:#0000FF;">Source</p> 
    <div style="font-family:'Times New Roman', Times, serif;font-size:12pt;"> 
     <a href="http://poj.org/searchproblem?field=source&amp;key=Noi+01" rel="nofollow">Noi 01</a> 
    </div></td> 
  </tr> 
 </tbody> 
</table>

\[[Submit][]\]   \[Go Back\]   \[[Status][]\]   \[[Discuss][]\]

废了老大劲， 开始自己dp用的二维，结果一直WA， 因为第i-1行的状态 不一定和你枚举的i-2行状态相匹配，所以要开三维数组， 而且这题时间卡的也挺紧，要预处理很多

#include<cstdio>
    #include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<vector>
    using namespace std;
    typedef long long ll;
    const ll mod=(ll)0x100000000;
    const int INF=0x3f3f3f3f;
    const int maxn=110;
    int n, m;
    char mp[110][11];
    int tu[110];
    vector<int> s;
    int dp[maxn][maxn][maxn], sum[maxn];
    
    int getsum(int x){
    	int cnt=0;
    	
    	while(x){
    		if(x&1) cnt++;
    		x>>=1;
    	}
    	return cnt;
    }
    
    void get_state(){
    	int cnt=0;
    	for(int i=0; i<(1<<m); i++)
    		if(!(i&(i<<2)) && !(i&(i<<1))){
    			 s.push_back(i);
    			 sum[cnt++]=getsum(i);
    		}
    }
    
    bool check(int x, int r){
    	if(x&tu[r])
    		return false;
    	else
    		return true;
    }
    
    
    
    void solve(){
    	for(int i=0; i<s.size(); i++)
    		if(check(s[i], 0))	dp[0][i][0]=sum[i];
    	if(n==1) return;
    	
    	for(int i=0; i<s.size(); i++)
    		for(int j=0; j<s.size(); j++)
    			if(check(s[j], 1) && !(s[j]&s[i])) dp[1][j][i]=max(dp[1][j][i], dp[0][i][0]+sum[j]);
    	if(n==2) return;
    	
    	for(int i=2; i<n; i++)
    	{
    		for(int a=0; a<s.size(); a++)
    		{
    			if(!check(s[a], i)) continue;
    			for(int b=0; b<s.size(); b++)
    			{
    				if(!check(s[b], i-1)) continue;
    				for(int c=0; c<s.size(); c++)
    				{
    					if(!check(s[c], i-2)) continue;
    					if(!(s[a]&s[b] || s[a]&s[c] || s[b]&s[c]))
    						dp[i][a][b]=max(dp[i][a][b], dp[i-1][b][c]+sum[a]);
    				}
    			}
    		}
    	}
    }
    
    int main(){
    	scanf("%d%d", &n, &m);
    	
    	for(int i=0; i<n; i++)
    	{
    		scanf("%s", mp[i]);
    		for(int j=0; j<m; j++)
    			if(mp[i][j]=='H') tu[i]+=1<<j;
    	}
    		
    	get_state();
    	
    	solve();
    	int ans=0;
    	
    	for(int i=0; i<s.size(); i++)
    		for(int j=0; j<s.size(); j++)
    			ans=max(ans, dp[n-1][i][j]);
    	
    	printf("%d\n", ans);
    	return 0;
    }

[Submit]: http://poj.org/submit?problem_id=1185
[Status]: http://poj.org/problemstatus?problem_id=1185
[Discuss]: http://poj.org/bbs?problem_id=1185