# 状压DP详解（2）--状态的预处理+经典例题剖析--POJ1185炮兵阵地

2021-07-19 19:42:58

## 炮兵阵地

Time Limit: 2000MS Memory Limit: 65536K

## Description

### Output

Sample Input

5 4
PHPP
PPHH
PPPP
PHPP
PHHP
Sample Output

6

``````//#include <bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
char s[105][12];
int a[105][12],m,n,b[105][12];
ll dp[105][1<<12];
const int inf=99999999;
int check(int s);
int main()
{
scanf ("%d%d",&n,&m);
for (int i=0; i<n; i++)
scanf ("%s",s[i]);
for (int i=0; i<n; i++)
for (int j=0; j<m; j++)
if (s[i][j]=='P') a[i][j]=1;
int ans=0;
for (int j=0; j<(1<<m); j++){
ans=max(ans,check(j));
}
printf ("%d\n",ans);
return 0;
}
int check(int s)
{
memset(b,0,sizeof(b));
for (int i=0; i<m; i++){
if ((s&(1<<i)) && !a[0][i]) return 0;
if ((s&(1<<i)) && (s&(1<<i+1))) return 0;
if ((s&(1<<i)) && (s&(1<<i+2))) return 0;
else if (s&(1<<i)) b[0][i]=1;
}
for (int i=1; i<n; i++){
for (int j=0; j<m; j++){
if (i==1) {
if (a[i][j] && !b[i-1][j]){
if (j==0) b[i][j]=1;
else if (j==1 && !b[i][j-1]) b[i][j]=1;
else if (j>1 && !b[i][j-1] && !b[i][j-2]) b[i][j]=1;
}
}
else {
if (a[i][j] && !b[i-1][j] && !b[i-2][j]){
if (j==0) b[i][j]=1;
else if (j==1 && !b[i][j-1]) b[i][j]=1;
else if (j>1 && !b[i][j-1] && !b[i][j-2]) b[i][j]=1;
}
}
}
}
int ans=0;
for (int i=0; i<n; i++)
for (int j=0; j<m; j++)
if (b[i][j]) ans++;
return ans;
}
```

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
```

``````fr(int i=0; i<(1<<m); i++)
if ((i&(i<<1))==0 && (i&(i<<2))==0) {
v[cnt++]=i;
int sum=0;
for(int j=0; j<(1<<m); j++) if ((i&(1<<j))) sum++;
num[cnt-1]=sum;
}
```

1.
2.
3.
4.
5.
6.
7.
```

``````fr (int i=0; i<n; i++) {
fr (for (int j=0; j<cnt; j++)) {
if (!ok(i,v[j])) continue;
if (i==0) {
//
continue;
}
```

1.
2.
3.
4.
5.
6.
7.
```

``````if (i==1) {
for(int k=0; k<cnt; k++) {//判断和上一行是否01交错
if ((v[j]&v[k])==0) //
}
}
```

1.
2.
3.
4.
5.
```
``````else {
for(int k=0; k<cnt; k++) {//对上一行状态的枚举
if ((v[j]&v[k])) continue;
for(int g=0; g<cnt; g++) {//对上上行的状态枚举
if ((v[j]&v[g]) || (v[k]&v[g])) continue;
//
}
}
}
```

1.
2.
3.
4.
5.
6.
7.
8.
9.
```

``````dp[i][j][k]=max(dp[i][j][k],dp[i-1][k][g]+num[j]);
```

1.
```

``````dp[i][j][0]=num[j];//第一行
dp[i][j][k]=max(dp[i-1][k][0]+num[j],dp[i][j][k]);//第二行
```

1.
2.
```

``````//#include <bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define fr(i,n) for (int i=0; i<n; i++)
using namespace std;
typedef long long ll;
char s[105][12];
int a[105][12],m,n,dp[102][65][65];
int v[65],num[65],ans=0;
int ok(int r,int s);
int main()
{
scanf ("%d%d",&n,&m);
memset(dp,0,sizeof(dp));
int cnt=0;
fr(i,(1<<m)) if ((i&(i<<1))==0 && (i&(i<<2))==0){
v[cnt++]=i;
int sum=0;
fr(j,m) if ((i&(1<<j))) sum++;
num[cnt-1]=sum;
}
fr(i,n) scanf ("%s",s[i]);
fr(i,n) fr(j,m) if (s[i][j]=='P') a[i][j]=1;
fr (i,n){
fr (j,cnt){
if (!ok(i,v[j])) continue;
if (i==0){
dp[i][j][0]=num[j];
continue;
}
if (i==1){
fr(k,cnt){
if ((v[j]&v[k])==0) dp[i][j][k]=max(dp[i-1][k][0]+num[j],dp[i][j][k]);
}
}
else {
fr(k,cnt) {
if ((v[j]&v[k])) continue;
fr(g,cnt){
if ((v[j]&v[g]) || (v[k]&v[g])) continue;
dp[i][j][k]=max(dp[i][j][k],dp[i-1][k][g]+num[j]);
}
}
}
}
}
fr(i,cnt) fr(j,cnt) ans=max(ans,dp[n-1][i][j]);
printf ("%d\n",ans);
return 0;
}
int ok(int r,int s)
{
fr(i,m) if ((s&(1<<i)) && !a[r][i]) return 0;
return 1;
}
```

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
```

https://blog.51cto.com/u_15249461/2870446