P2704 [NOI2001]炮兵阵地

依旧是状态压缩DP（什么叫依旧是，这不是第一道吗）

题目大意

有N*M个方格，每个方格是平原（“P”）或者山地（“H”），如果是平原则可以布置炮兵

每个炮兵的攻击范围是向上向下两格，向左向右两格，以及自己共5格，在攻击范围内不能再布置炮兵，问最多布置多少炮兵

输入输出格式

输入格式：

 

第一行包含两个由空格分割开的正整数，分别表示N和M；

接下来的N行，每一行含有连续的M个字符（‘P’或者‘H’），中间没有空格。按顺序表示地图中每一行的数据。N≤100；M≤10。

 

输出格式：

 

仅一行，包含一个整数K，表示最多能摆放的炮兵部队的数量。

solution

这道题设计状态比较难（对于我来说），但可以考虑一定是从上向下DP的，因此需要记录的状态只有这一行以及上一行（注意，只用记录两行，如果只用一维记录会无法记录状态，三维会MLE），上上行可以通过另一维来得到而且不会MLE

用DP[L][S][i]表示当前是第i行，这一行状态是S,上一行状态是L,那么DP[L][S][i]=max(DP[L][S][i],DP[Fl][L][i-1]+sum[S]);   sum[S]表示S这个状态1的个数（即炮兵的个数）

DP比较重要的是设置边界预处理，那么只需要处理前两行的DP值就可以了

几点需要注意的：

1.DP数组第三维需要滚动，不然MLE，考虑到一行的状态只跟上行和上上行有关，所以%3即可

2.DP的优化：DP在枚举行的同时要枚举三个状态，如果放到最里面判断则O(n*2^3m)，TLE妥妥的，因此每次枚举状态都进行判断，这样可以极大的缩短时间

code

#include<cstdio> #include<iostream> #define re register using namespace std; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int getsum(int x) { int ans=0; while(x) { if(x&1) ans++; x>>=1; } return ans; } int sum[1<<10],all,anss; int ans,sta[105],DP[1<<10][1<<10][3],n,m; char map[105][12]; int main() { n=read();m=read(); all=(1<<m)-1; for(re int i=0;i<n;++i) for(re int j=0;j<m;++j) { cin>>map[i][j]; if(map[i][j]=='H') sta[i]|=(1<<(m-1-j)); } // for(re int i=0;i<n;++i) // printf("%d\n",sta[i]); for(int i=0;i<=all;++i) sum[i]=getsum(i); for(re int S=0;S<=all;++S) if(!(S&sta[0]||(S&(S<<1))||(S&(S<<2)))) DP for(re int L=0;L<=all;++L) for(re int S=0;S<=all;++S) if(!(L&S||L&sta[0]||S&sta[1]||(L&(L<<1))||(L&(L<<2))||(S&(S<<1))||(S&(S<<2)))) DP[L][S][1]=sum[S]+sum[L]; for(re int i=2;i<n;++i) for(re int L=0;L<=all;++L) { if(L&sta[i-1]||(L&(L<<1))||(L&(L<<2))) continue; for(re int S=0;S<=all;++S) { if(S&sta[i]||L&S||(S&(S<<1))||(S&(S<<2))) continue; for(re int FL=0;FL<=all;++FL) { if(FL&L||FL&S||FL&sta[i-2]||(FL&(FL<<1))||(FL&(FL<<2))) continue; DP[L][S][i%3]=max(DP[L][S][i%3],DP[FL][L][(i-1)%3]+sum[S]); } } } for(re int L=0;L<=all;++L) for(re int S=0;S<=all;++S) anss=max(anss,DP[L][S][(n-1)%3]); printf("%d\n",anss); return 0; }

 

转载于:https://www.cnblogs.com/Liuz8848/p/10852533.html