POJ - 1185 炮兵阵地 (插头dp)

题目链接

明明是道状压dp的题我为啥非要用插头dp乱搞啊

逐行枚举，设dp[i][S]为枚举到第i个格子时，状态为S的情况。S为当前行上的“插头”状态，每两个二进制位表示一个格子，设当前格子为(x,y)，则y之前的插头表示左插头，y之后的插头表示上插头，仅当当前格子上没有插头时才能够放置炮兵。转移的大致流程为：枚举当前状态->判断是否可放置炮兵->更新右插头状态->更新上插头状态。

跑的速度还可以，虽然略输于状压dp。如果合法状态数不是那么少的话，可能会比状压dp要快。

 #include<cstdio>

 #include<cstring>

 using namespace std;

 typedef long long ll;

 const int N=+,inf=0x3f3f3f3f;

 char s[N][];

 struct Hashmap {

     static const int N=1e5+;

     int hd[N],nxt[N],fa[N],p[N],q[N],tot;

     Hashmap() {memset(hd,-,sizeof hd),tot=;}

     void clear() {for(int i=; i<tot; ++i)hd[fa[i]]=-; tot=;}

     int size() {return tot;}

     int& operator[](int x) {

         int u=x%N;

         for(int i=hd[u]; ~i; i=nxt[i]) {if(p[i]==x)return q[i];}

         p[tot]=x,q[tot]=,fa[tot]=u,nxt[tot]=hd[u],hd[u]=tot++;

         return q[tot-];

     }

 } dp[];

 int n,m;

 int get(int S,int y) {return y>=?S>>(*y)&:;}

 int Set(int S,int y,int f) {return y>=?(S&~(<<(*y)))|(f<<(*y)):;}

 int Max(int S,int y,int f) {return get(S,y)<f?Set(S,y,f):S;}

 int sub(int S,int y) {return get(S,y)?Set(S,y,get(S,y)-):S;}

 int put(int S,int y) {

     for(int i=y+; i<=y+; ++i)S=Max(S,i,);

     S=Max(S,y,);

     return S;

 }

 void upd(int& x,int y) {if(x<y)x=y;}

 int main() {

     scanf("%d%d",&n,&m);

     for(int i=; i<n; ++i)scanf("%s",s[i]);

     dp[][]=;

     for(int t=; t<n*m; ++t) {

         dp[t&^].clear();

         int x=t/m,y=t%m;

         for(int i=; i<dp[t&].size(); ++i) {

             int S=dp[t&].p[i],now=dp[t&].q[i];

             upd(dp[t&^][sub(S,y)],now);

             if(s[x][y]=='P'&&!get(S,y))upd(dp[t&^][put(S,y)],now+);

         }

     }

     int ans=;

     for(int i=; i<dp[(n*m)&].size(); ++i)upd(ans,dp[(n*m)&].q[i]);

     printf("%d\n",ans);

     return ;

 }