POJ

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

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

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

 1 #include<cstdio>
 2 #include<cstring>
 3 using namespace std;
 4 typedef long long ll;
 5 const int N=100+10,inf=0x3f3f3f3f;
 6 char s[N][15];
 7 struct Hashmap {
 8     static const int N=1e5+3;
 9     int hd[N],nxt[N],fa[N],p[N],q[N],tot;
10     Hashmap() {memset(hd,-1,sizeof hd),tot=0;}
11     void clear() {for(int i=0; i<tot; ++i)hd[fa[i]]=-1; tot=0;}
12     int size() {return tot;}
13     int& operator[](int x) {
14         int u=x%N;
15         for(int i=hd[u]; ~i; i=nxt[i]) {if(p[i]==x)return q[i];}
16         p[tot]=x,q[tot]=0,fa[tot]=u,nxt[tot]=hd[u],hd[u]=tot++;
17         return q[tot-1];
18     }
19 } dp[2];
20 int n,m;
21 int get(int S,int y) {return y>=0?S>>(2*y)&3:0;}
22 int Set(int S,int y,int f) {return y>=0?(S&~(3<<(2*y)))|(f<<(2*y)):0;}
23 int Max(int S,int y,int f) {return get(S,y)<f?Set(S,y,f):S;}
24 int sub(int S,int y) {return get(S,y)?Set(S,y,get(S,y)-1):S;}
25 int put(int S,int y) {
26     for(int i=y+1; i<=y+2; ++i)S=Max(S,i,1);
27     S=Max(S,y,2);
28     return S;
29 }
30 void upd(int& x,int y) {if(x<y)x=y;}
31 int main() {
32     scanf("%d%d",&n,&m);
33     for(int i=0; i<n; ++i)scanf("%s",s[i]);
34     dp[0][0]=0;
35     for(int t=0; t<n*m; ++t) {
36         dp[t&1^1].clear();
37         int x=t/m,y=t%m;
38         for(int i=0; i<dp[t&1].size(); ++i) {
39             int S=dp[t&1].p[i],now=dp[t&1].q[i];
40             upd(dp[t&1^1][sub(S,y)],now);
41             if(s[x][y]=='P'&&!get(S,y))upd(dp[t&1^1][put(S,y)],now+1);
42         }
43     }
44     int ans=0;
45     for(int i=0; i<dp[(n*m)&1].size(); ++i)upd(ans,dp[(n*m)&1].q[i]);
46     printf("%d
",ans);
47     return 0;
48 }