poj砲兵陣地(状圧)(25+10+20=55)
16916 ワード
http://poj.org/problem?id=1185
最初は考えが間違っていたので、この行を保存した状態で前の2行の状態を列挙すると、前の2行の状態が同時に要求を満たすことは保証されません.
2行の状態を保存して、前の
いろいろな小さな間違いが絶えない.
View Code
最初は考えが間違っていたので、この行を保存した状態で前の2行の状態を列挙すると、前の2行の状態が同時に要求を満たすことは保証されません.
2行の状態を保存して、前の
いろいろな小さな間違いが絶えない.
1 #include <iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5 #include<stdlib.h>
6 using namespace std;
7 char c;
8 int p[12],o[1050],dp[2][1050][1050],f[110],x[1050];
9 int main()
10 {
11 int i,j,n,m,e,a,k,g;
12 while(scanf("%d%d",&n,&m)!=EOF)
13 {
14 memset(p,0,sizeof(p));
15 memset(f,0,sizeof(f));
16 memset(o,0,sizeof(o));
17 p[0] = 1;
18 for(i = 1; i <= 12 ; i++)
19 p[i] = p[i-1]*2;
20 for(i = 0 ; i < n ; i++)
21 {
22 getchar();
23 for(j = 0 ; j < m ; j++)
24 {
25 scanf("%c",&c);
26 if(c=='P')
27 f[i]+=p[j];
28 }
29 }
30 memset(dp,0,sizeof(dp));
31 k = 0;
32 for(i =0 ; i < 1<<m ; i++)
33 {
34 if((i&(i<<1)))
35 continue;
36 if((i&(i>>1)))
37 continue;
38 if((i&(i>>2)))
39 continue;
40 if((i&(i<<2)))
41 continue;
42 for(e = 0 ; e < m ; e++)
43 if((i&(1<<e))!=0)
44 o[i]++;
45 k++;
46 x[k] = i;
47 }
48 for(i = 1; i <= k ;i++)
49 if((x[i]&(f[1]))==x[i])
50 {
51 for(j = 1; j <= k ; j++)
52 if((x[j]&(f[0]))==x[j]&&(x[i]&x[j])==0)
53 dp[1][i][j] = o[x[i]]+o[x[j]];
54 }
55 for(i = 2 ; i < n ; i++)
56 {
57 for(j = 1; j <= k ;j++)
58 {
59 if((x[j]&f[i])!=x[j])
60 continue;
61 for(g = 1; g <= k ; g++)
62 {
63 if(x[g]&x[j])
64 continue;
65 if((x[g]&(f[i-1]))!=x[g])
66 continue;
67 for(a = 1; a <= k ; a++)
68 {
69 if((x[a]&(f[i-2]))!=x[a])
70 continue;
71 if(x[a]&x[j])
72 continue;
73 dp[i%2][j][g] = max(dp[i%2][j][g],dp[(i-1)%2][g][a]+o[x[j]]);
74 }
75 }
76 }
77 }
78 int ans=0;
79 if(n==1)
80 {
81 for(i = 1; i <= k ; i++)
82 if((f[0]&x[i])==x[i])
83 ans = max(o[x[i]],ans);
84 }
85 else
86 {
87 for( i =1; i <= k ; i++)
88 for(j = 1; j <= k ; j++)
89 ans = max(ans,dp[(n-1)%2][i][j]);
90 }
91 printf("%d
",ans);
92 }
93 return 0;
94 }
95 /*
96 14 10
97 PPPPPPPPPP
98 PPPPPPPPPP
99 HHHHHHHHHH
100 PPPPPPPPPP
101 HHHHHHHHHH
102 HHHHHHHHHH
103 PPPPPPPPPP
104 PPPPPPPPPP
105 PPPPPPPPPP
106 HHHHHHHHHH
107 PPPPPPPPPP
108 HHHHHHHHHH
109 HHHHHHHHHH
110 PPPPPPPPPP
111 */
112 /*
113 3 4
114 PHPP
115 PPHH
116 PPPP
117 */View Code